Sort（排序）

Sort排序动画

quick_sort

Step:

• 第一步，选择一个基准数x，可以选当前数组的最后一个元素，第一个元素或者数组中间元素
• 第二步，双指针扫描（调整区间），设定i指向当前排序区间的左端点 - 1，设定j指向当前排序区间的右端点 + 1， 如果 i < j那么执行循环，首先左边i指针指向元素如果小于基准数则i指针右移，找到第一个i < j && a[i] >= x的数；其次右边j指针指向元素如果大于基准数则j指针左移，找到第一个i < j && a[j] >= x的数；如果此时i < j, 则将i指针指向的值和j指针指向的值交换；
• 第二步会将小于x的数乱序排到x的左边，将大于x的数乱序排到x的右边，即完成一趟排序，接下来要做的是递归的排序x的左边和x的右边区间即可

#include 
using namespace std;

const int N = 1e5 + 5;
int a[N];

void quick_sort1(int l, int r);
void quick_sort2(int l, int r);

int main(void)
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i ++)
	{
		scanf("%d", &a[i]);
	}
	quick_sort2(0, n - 1);

	for (int i = 0; i < n; i ++)
	{
		printf("%d ", a[i]);
	}

	return 0;
}

// do-while version
void quick_sort1(int l, int r)
{
	if (l >= r)
	{
		return ;
	}
	int mid = (l + r) >> 1;
	int x = a[mid];
	int i = l - 1, j = r + 1;
	while (i < j)
	{
		do
		{
			i ++;
		} 
		while (a[i] < x);

		do
		{
			j --;
		}
		while (a[j] > x);
		if (i < j)
		{
			swap(a[i], a[j]);
		}
	}
	quick_sort1(l, j);
	quick_sort1(j + 1, r);
}


// while version
void quick_sort2(int l, int r)
{
	if (l >= r)
	{
		return ;
	}
	int mid = (l + r) >> 1;
	int x = a[mid];
	int i = l - 1, j = r + 1;
	while (i < j)
	{
		while (a[++i] < x)
		{
		  
		}


		while (a[--j] > x) 
		{
		  
		}

		if (i < j)
		{
			swap(a[i], a[j]);
		}
	}
	quick_sort2(l, j);
	quick_sort2(j + 1, r);
}

第K个数（TopK问题）

题意：求数组中第K个小或第K个大的数是多少, 或者求前K个小或前K个大的数

• 解法1： Sort一遍，返回数组第k个元素即可O(nlogn)

  • #include 
    using namespace std;
    
    const int N = 1e5 + 5;
    
    int a[N];
    
    int main(void)
    {
    	int n, k;
    	scanf("%d%d", &n, &k);
    	for (int i = 0; i < n; i ++)
    	{
    		scanf("%d", &a[i]);
    	}
    	sort(a, a + n);
    	printf("%d\n", a[k - 1]);
    	return 0;
    }
    

• 解法2：快排分治 O(N)
  • 首先考虑快排的思想，对于第K小的数来看，快排每次选择一个基准x，将比基准x小的数排到左边，将比基准x大的数排到右边，而一趟下来我们就知道<=x的元素个数有numLeft个，而此时我们可以比较k与numLeft的个数，如果k < numleft, 则我们就在区间的左边找第K小的数；反之在区间的右边找第k - numLeft小的数即可
  • 对于前K小的数来看，一样依照上面的思路只不过每次我们需要返回的是一个范围的数

  • #include 
    using namespace std;
    
    const int N = 1e5 + 5;
    
    int a[N];
    vector arr;
    priority_queue q; // 大根堆
    
    int _knum(int l, int r, int k);
    vector _knums(vector& arr, int l, int r, int k);
    vector _knums1(vector& arr, int k);
    
    int main(void)
    {
    	int n, k, input;
    	scanf("%d%d", &n, &k);
    	for (int i = 0; i < n; i ++)
    	{
    		scanf("%d", &input);
    		// scanf("%d", &a[i]);
    		arr.push_back(input);
    	}
    	// int res = _knum(0, n - 1, k);
    	// printf("%d\n", res);
    	vector res = _knums(arr, 0, arr.size() - 1, k);
    	for (auto &i: res)
    	{
    		printf("%d ", i);
    	}
    	return 0;
    }
    
    // 求单个第K小方案
    int _knum(int l, int r, int k)
    {
    	if (l >= r) return a[l];
    	int x = a[(l + r) >> 1];
    	int i = l - 1, j = r + 1;
    	while (i < j)
    	{
    		do
    		{
    			i ++;
    		}
    		while (a[i] < x);
    
    		do
    		{
    			j --;
    		}
    		while (a[j] > x);
    		if (i < j)
    		{
    			swap(a[i], a[j]);
    		}
    	}
    	int numLeft = j - l + 1;
    	if (k <= numLeft)
    	{
    		return _knum(l, j, k);
    	}
       	else 
    	{
    		return _knum(j + 1, r, k - numLeft);
    	}
    }
    
    vector _knums(vector& arr, int l, int r, int k)
    {
    	int x = arr[l];
    	int i = l, j = r;
    	while (i < j)
    	{
    		while (i < j && arr[j] >= x) j --;
    		while (i < j && arr[i] <= x) i ++;
    
    		swap(arr[i], arr[j]);
    	}
    	swap(arr[i], arr[l]);
    	if (i > k)
    	{
    		return _knums(arr, l, i - 1, k);
    	}
    	if (i < k) 
    	{
    		return _knums(arr, i + 1, r, k);
    	}
    
    	vector tmp;
    	tmp.assign(arr.begin(), arr.begin() + k);
    	return tmp;
    }
    
    vector _knums1(vector& arr, int k) 
    {
    	for (auto &i : arr)
    	{
    		if (q.size() < k)
    		{
    			q.push(i);
    		} 
    		else if (q.top() > i)
    		{
    			q.pop();
    			q.push(i);
    		}
    	}
    	vector tmp;
    	while (!q.empty())
    	{
    		tmp.push_back(q.top());
    		q.pop();
    	}
    	return tmp;
    }
    

• 解法3：优先队列（堆）,O(NlogK)
  • 如果求第K个数，用小根堆存储元素，然后在pop出来n - k个元素
  • 如果求前K个数，比如前K小，用大根堆存储一个容量为K的堆，每次pop出最大的数，堆中保留的就是前K小个数；前K大反向操作即可；

  • #include 
    using namespace std;
    
    const int N = 1e5 + 5;
    
    priority_queue q;
    
    int main(void)
    {
    	int n, k, x;
    	scanf("%d%d", &n, &k);
    	for (int i = 0; i < n; i ++)
    	{
    		scanf("%d", &x);
    		q.push(x);
    	}
    	while (n > k)
    	{
    		q.pop();
    	}
    	printf("%d\n", q.top());
    	return 0;
    }
    

• 解法4：平衡二叉搜索树（红黑树O(NlogK)) Set

  • 
    #include 
    using namespace std;
    
    const int N = 1e5 + 5;
    
    // priority_queue q;
    multiset S;
    
    int main(void)
    {
    	int n, k, x;
    	scanf("%d%d", &n, &k);
    	for (int i = 0; i < n; i ++)
    	{
    		scanf("%d", &x);
    		S.insert(x);
    	}
    	int res = 0;
    	for (auto t: S)
    	{
    	    k --;
    	    if (k == 0)
    	    {
    	        res = t;
    	    }
    	}
    	printf("%d\n", res);
    	return 0;
    }
    

  • 解法5： 桶排序（数组内元素范围不大的情况下）O(n)

归并排序

• 确定分界点
• 递归左右区间
• 合并子问题

• void merge_sort(int l, int r)
  {
  	if (l >= r) // 递归出口
  	{
  		return ;
  	}
  	int mid = (l + r) >> 1; // 确定分界点
  	merge_sort(l, mid); // 划分左区间
  	merge_sort(mid + 1, r); // 划分右区间
  	int k = 0, i = l, j = mid + 1;
  	while (i <= mid && j <= r)
  	{
  		if (a[i] < a[j]) 
  		{
  			tmp[k] = a[i];
  			k ++;
  			i ++;
  		}
  		else 
  		{
  			tmp[k] = a[j];
  			k ++;
  			j ++;
  		}
  	}
  	while (i <= mid) // 还剩下元素没有加入tmp中
  	{
  		tmp[k] = a[i];
  		k ++;
  		i ++;
  	}
  	while (j <= r)
  	{
  		tmp[k] = a[j];
  		k ++;
  		j ++;
  	}
  	for(i = l, j = 0; i <= r; i ++, j ++)
  	{
  		a[i] = tmp[j];
  	}
  }
  

求解数组中的逆序数

• 逆序对的定义如下：对于数列的第 i个和第 j个元素，如果满足 i<j且 a[i]>a[j]，则其为一个逆序对；否则不是。
• 归并排序求逆序数O(nlogn)
  • 在归并排序中的第三步我们去遍历左区间和右区间时会比较左区间中第i个元素与右区间的第j个元素，它们的相对位置属于i < j, 如果此时满足a[i] > a[j], 则满足逆序数的定义， 并且针对于当前j，有 mid -i + 1个元素会与当前j成为逆序数。 why ？ 因为针对于左区间[i, mid]和右区间[mid + 1, r], 在经历划分合并时已经有序， 左区间和右区间都是单调递增，所以针对于i < j && a[i] > a[j]时，[i, mid]之间的所有元素都和当前j是逆序数。

  • #include 
    
    using namespace std;
    
    const int N = 1e5 + 5;
    
    int a[N], tmp[N]; // tmp数组辅助记录
    long long res = 0;
    
    void merge_sort(int l, int r);
    
    int main(void)
    {
    	int n;
    	scanf("%d", &n);
    	for (int i = 0; i < n; i ++)
    	{
    		scanf("%d", &a[i]);
    	}
    	merge_sort(0, n - 1);
    	// for (int i = 0; i < n; i ++)
    	// {
    	// 	printf("%d ", a[i]);
    	// }
    	printf("%lld\n", res);
    	return 0;
    }
    
    void merge_sort(int l, int r)
    {
    	if (l >= r) // 递归出口
    	{
    		return ;
    	}
    	int mid = (l + r) >> 1; // 确定分界点
    	merge_sort(l, mid); // 划分左区间
    	merge_sort(mid + 1, r); // 划分右区间
    	int k = 0, i = l, j = mid + 1;
    	while (i <= mid && j <= r)
    	{
    		if (a[i] <= a[j]) 
    		{
    			tmp[k] = a[i];
    			k ++;
    			i ++;
    		}
    		else 
    		{
    			tmp[k] = a[j];
    			k ++;
    			j ++;
    			res += mid - i + 1;
    		}
    	}
    	while (i <= mid) // 还剩下元素没有加入tmp中
    	{
    		tmp[k] = a[i];
    		k ++;
    		i ++;
    	}
    	while (j <= r)
    	{
    		tmp[k] = a[j];
    		k ++;
    		j ++;
    	}
    	for(i = l, j = 0; i <= r; i ++, j ++)
    	{
    		a[i] = tmp[j];
    	}
    }
    

• 树状数组（待更）

二分模板

• lower_bound()，查找第一个>=x的元素的位置

  • int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (a[mid] < x)
        {
            l = mid + 1;
        }
        else 
        {
            r = mid;
        }
    }
    

  • 当a[mid]小于x时，令l = mid + 1，mid及其左边的位置被排除了，可能出现解的位置是mid + 1及其后面的位置；当a[mid] >= x时，说明mid及其左边可能含有值为x的元素；当查找结束时，l与r相遇，l所在元素若是x则一定是x出现最小位置，因为l左边的元素必然都小于x。

• upper_bound(), 查找最后一个<=x的元素的位置

  • int l = 0, r = n;
    while (l + 1 < r)
    {
        int mid = l + r >> 1;
        if (a[mid] <= x)
        {
            l = mid;
        }
        else 
        {
            r = mid;
        }
    
    }
    

  • 当a[mid] <= x时，待查找元素只可能在mid及其后面，所以l = mid；当a[mid] > x时，待查找元素只会在mid左边，令r = mid。为什么不令r = mid - 1呢？因为如果按照上一个二分的写法，循环判断条件还是l < r,当只有两个元素比如2 2时，l指向第一个元素，r指向第二个元素，mid指向第一个元素，a[mid] <= x，l = mid还是指向第一个元素，指针不移动了，陷入死循环了，此刻l + 1 == r，未能退出循环。那么直接把循环判断条件改成l + 1 < r呢？此时一旦只有两个元素，l和r差1，循环便不再执行，查找错误。所以这里出现了二分的典型错误，l == r作为循环终止条件，会出现死循环，l + 1 == r作为循环终止条件，会出现查找错误。

• #include 
  
  using namespace std;
  
  const int N = 1e5 + 5;
  
  int lower_binary_search(int a[], int l, int r, int x);
  int upper_binary_search(int a[], int l, int r, int x);
  
  int a[N];
  
  int main(void)
  {
  	int n, q, k;
  	scanf("%d%d", &n, &q);
  	for (int i = 0; i < n; i ++)
  	{
  		scanf("%d", &a[i]);
  	}
  	while (q --)
  	{
  		scanf("%d", &k);
  		int left = lower_binary_search(a, 0, n - 1, k);
  		if (left == - 1)
  		{
  			printf("-1 -1\n");
  			continue;
  		}
  		int right = upper_binary_search(a, 0, n, k);
  		printf("%d %d\n", left, right);
  	}
  	return 0;
  }
  
  int lower_binary_search(int a[], int l, int r, int x)
  {
  	while (l < r)
  	{
  		int mid = (l + r) >> 1;
  		if (a[mid] < x)
  		{
  			l = mid + 1;
  		}
  		else 
  		{
  			r = mid;
  		}
  
  	}
  	if (a[l] == x)
  	{
  		return l;
  	}
  	return -1;
  }
  
  int upper_binary_search(int a[], int l, int r, int x)
  {
  	while (l + 1 < r)
  	{
  		int mid = (l + r) >> 1;
  		if (a[mid] <= x)
  		{
  			l = mid;
  		}
  		else 
  		{
  			r = mid;
  		}
  	}
  	if (a[l] == x)
  	{
  		return l;
  	}
  	return -1;
  }
  

浮点数二分

• 数的三次方根， desc：给定一个浮点数n求它的三次方根

  • 二分(logn): 从 答案范围-10000.0 ~ 10000.0开始二分，找到二分后的数的三次方即可， 而终止条件应该为r - l >= eps(浮点数的一个常数值)

  • #include 
    
    using namespace std;
    
    const double eps = 1e-7;
    
    int main(void)
    {
    	double n;
    	scanf("%lf", &n);
    	double l = -10000.0, r = 10000.0;
    	while (r - l >= eps)
    	{
    		double mid = (l + r) / 2.0;
    		if (mid * mid * mid <= n)
    		{
    			l = mid;
    		}
    		else 
    		{
    			r = mid;
    		}
    	}
    	printf("%.6lf\n", l);
    	return 0;
    }
    

• 剑指Offer72， 求平方根

  • 给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。正数的平方根有两个，只输出其中的正数平方根。如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
  • 传送门
  • 数据范围是\(0\) ~ \(2^{31} - 1\) ， 我们可以去二分答案，二分范围是0 ~ x, 用模板二upper_binary_search即可，注意要开long long!!!, 因为二分的答案的平方和x去比较，不开long long 会wa掉

  • class Solution {
    public:
        typedef long long LL;
        int mySqrt(int x) {
            if (x <= 1) return x;
            LL l = 0, r = x;
            while (l + 1 < r)
            {
                LL mid = (l + r) >> 1;
                if (mid * mid <= x)
                {
                    l = mid;
                }
                else 
                {
                    r = mid;
                }
            }
            return (int)l;
        }
    };
    

前缀和

• 一维前缀和
  • 首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。
  • 求区间[l, r]的区间和，可以被计算为sum[r] - sum[l - 1]

  • #include 
    
    using namespace std;
    
    const int N = 1e5 + 5;
    int a[N], sum[N];
    
    int main(void)
    {
    	int n, m;
    	scanf("%d%d", &n, &m);
    	for (int i = 0; i < n; i ++)
    	{
    		scanf("%d", &a[i]);
    	}
    	for (int i = 1; i <= n; i ++)
    	{
    		sum[i] = sum[i - 1] + a[i - 1];
    	}
    	int l, r;
    	while (m --)
    	{
    		scanf("%d%d", &l, &r);
    		printf("%d\n", sum[r] - sum[l - 1]);
    	}
    	return 0;
    }
    

• 二维前缀和
  • 二维前缀和即为以左上角为起点右下角为终点的这一块矩形区域。
  • 二维前缀和 sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + a[i - 1][j - 1] - sum[i - 1][j- 1]
  • 求区间[x1, y1]为左上角， 区间[x2, y2]为右下角的矩阵和可以等价于sum[x2][y2] - sum[x1 - 1, y2] - sum[x2, y1 - 1] + sun[x1 - 1, y1 - 1]

  • #include 
    
    using namespace std;
    
    const int MAXN = 1005;
    
    typedef long long LL;
    
    LL a[MAXN][MAXN], sum[MAXN][MAXN];
    
    int main(void)
    {
    	int n, m, q, x1, x2, y1, y2;
    	scanf("%d%d%d", &n, &m, &q);
    	for (int i = 0; i < n; i ++)
    	{
    		for(int j = 0; j < m; j ++)
    		{
    			scanf("%lld", &a[i][j]);
    		}
    	}
    	for (int i = 1; i <= n; i ++)
    	{
    		for (int j = 1; j <= m; j ++)
    		{
    			sum[i][j] = sum[i][j - 1] + sum[i - 1][j] + a[i - 1][j - 1] - sum[i - 1][j - 1]; 
    		}
    	}
    
    	while (q --)
    	{
    		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    		printf("%lld\n", sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);
    	}
    	return 0;
    }
    

差分

• 一维差分

  • 对询问q次， 每次区间[l, r]加上c， 求q次询问后，整个数组的值

  • 差分定义：

    • 首先给定一个原数组a：a[1], a[2], a[3]...a[n];
    • 然后我们构造一个数组b ： b[1] ,b[2] , b[3]...b[i];
    • 使得 a[i] = b[1] + b[2]+ b[3] +... + b[i]
    • 也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说,每一个a[i]都是b数组中从头开始的一段区间和。
    • 构造差分最为直接的方法为b[n] = a[n] - a[n - 1]
    • 差分数组b的前缀和为a数组本身

  • 如果我们构造好差分数组，每次区间[l, r]加上c, 我们可以视为对查分数组b[l] += c， 对b[r + 1] -= c我们对[l,r]的区间的差分都加上c等同于在原数组该区间都加上c,我们假定对左端点l加上c，那么l之前的所有数和l的差分都会比之前多c，而如果对r + 1端点减去c代表r+1之后的所有数比端点r多c， 即等同于对区间[l, r]加上c.

  • #include 
    
    using namespace std;
    
    const int N = 1e5 + 5;
    
    int a[N], diff[N], ans[N];
    
    int main()
    {
    	int n, m, l, r, c;
    	scanf("%d%d", &n, &m);
    	for (int i = 1; i <= n; i ++)
    	{
    		scanf("%d", &a[i]);
    	}
    	for (int i = 1; i <= n; i ++)
    	{
    		diff[i] = a[i] - a[i - 1];
    	}
    	while (m --)
    	{
    		scanf("%d%d%d", &l, &r, &c);
    		diff[l] += c;
    		diff[r + 1] -= c;
    	}
    	for (int i = 1; i <= n; i ++)
    	{
    		ans[i] = ans[i - 1] + diff[i];
    	}
    	for (int i = 1; i <= n; i ++)
    	{
    		printf("%d ", ans[i]);
    	}
    	return 0;
    }
    

• 二维差分矩阵
  • a数组是原数组diff数组是a数组的差分数组， 而a数组也是diff数组的前缀和数组， 构造差分数组diff使得a数组中a[i][j]是diff数组左上角[1, 1]到右下角[i, j]所包围矩形元素的和。
  • a数组是diff数组的前缀和数组，比如对diff数组的diffi][j]的修改，会影响到a数组中从a[i][j]及其往后的每一个数。
  • 

  • #include 
    
    using namespace std;
    
    const int N = 1005;
    
    int a[N][N], diff[N][N];
    
    void insert(int x1, int y1, int x2, int y2, int c);
    
    int main()
    {
    	int n, m, q, x1, y1, x2, y2, c;
    	scanf("%d%d%d", &n, &m, &q);
    	for (int i = 1; i <= n; i ++)
    	{
    		for (int j = 1; j <= m; j ++)
    		{
    			scanf("%d", &a[i][j]);
    		}
    	}
    	for (int i = 1; i <= n; i ++)
    	{
    		for (int j = 1; j <= m; j ++)
    		{
    			insert(i, j, i, j, a[i][j]);
    		}
    	}
    	while (q --)
    	{
    		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
    		insert(x1, y1, x2, y2, c);
    	}
    	for (int i = 1; i <= n; i ++)
    	{
    		for (int j = 1; j <= m; j ++)
    		{
    			diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
    		}
    	}
    	for (int i = 1; i <= n; i ++)
    	{
    		for (int j = 1; j <= m; j ++)
    		{
    			printf("%d ", diff[i][j]);
    		}
    		puts("");
    	}
    	return 0;
    }
    
    void insert(int x1, int y1, int x2, int y2, int c)
    {
    	diff[x1][y1] += c;
    	diff[x2 + 1][y1] -= c;
    	diff[x1][y2 + 1] -= c;
    	diff[x2 + 1][y2 + 1] += c;
    }