算法学习（七）—— 分治

关于分治

分治，就是“分而治之”的意思，就是把一个大问题，转化为若干个相同或者相似的几个子问题，然后在子问题的基础上再进行划分，直到能够快速一个子问题时停止划分

我们的快速排序和归并排序就是典型的分治思想

部分OJ题详解

分治-快排

75. 颜色分类

75. 颜色分类 - 力扣（LeetCode）

通过这个题目我们要来学习下“把数组分三段”这个思想，这个题目就是这样，以1为“基准元素”，左边全是小于1的，右边全是大于1的。我们来分析下这道题：

•  这道题其实就是在本系列第一道题 “ 移动0 ” 的双指针基础上多了一个指针，所以这道题的解法可以说是“三指针”
• 我们把一个数组分成三部分，0，1和2各自一部分，定义第一个指针i，用来遍历整个数组；定义第二个指针left，作用是标定0这个区域的最右侧；定义第三个指针right，作用是标记2这个区域的最左侧，正确的结果是，i走到数组结尾，left和right分别在1区域的左右位置
• 

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int left = -1, right = n, i = 0;while(i < right){if(nums[i] == 0){swap(nums[++left], nums[i++]);}else if(nums[i] == 1){i++;}else{swap(nums[--right], nums[i]);}}}
};

 912. 快速排序数组

 912. 排序数组 - 力扣（LeetCode）

这道题就是快排，把数组排成升序，下面来分析下这道题：

• 快排的思想就是，选一个中间值key，使key左边的值全都小于key，右边的值全都大于key，然后再在左右两边的区域采用相同的策略，就能达到快速排序；但是这种办法有个缺点，当数组里的数字全部是一样的时候，时间复杂度就会退化到(N ^ 2)
• 所以我们用分治的“数组分三块”的思想，来实现并优化快排。我们依旧把数组分成三个区域，左边的区域<key，中间区域==key，右边区域>key；然后就是和上面颜色划分一样，定义三个指针，每个指针的作用相同
• 
• 优化：有很多，比如三数取中，但是快排算法时间复杂度要接近O(N * logN)，需要用随机的方式选择基准元素，这个在“算法导论：概率求期望”里面有证明
• r = rand(); 然后我们获得随机基准元素的方式就是return nums[r % (right - left + 1) + left];

然后我们就可以用短短30行代码实现之前差不多100行的快排算法：

class Solution {
public:
vector<int> sortArray(vector<int>& nums) {srand(time(nullptr)); //种随机数种子qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vector<int>& nums, int l, int r){if(l >= r) return; //递归出口//数组分三份//1，随机选择基准元素int a = rand();int key = nums[a % (r - l + 1) + l];//2，定义三指针int i = l, left = l - 1, right = r + 1;//3，分类讨论while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}//走到这里，就分成了三段区域//[l, left]  [left + l, right - l]  [right, r]，其中中间已经排好了，只需要递归去排左边和右边qsort(nums, l, left);qsort(nums, right, r);}
};

215. 数组中第k个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

这个题目其实就是Top K 问题，这种问题有四种问法：①第K大  ②第K小  ③前K大  ④前K小

可以使用堆排序解决，另一个就是可以使用快速选择算法，前者时间复杂度为O(NlogN)，后者为O(N)，《算法导论》对这些时间复杂度有证明，这里我们主要讲后者 

下面我们来解释下这道题：

• 先选择基准元素key，也是分成三段，和上一题一样；由于题目是要找第K大的元素，所以我们只需要保证这个“第K大的元素”落在>key的区域，这样左边两个区域就不用再考虑了，只需要在>key的区域找就行了
• 所以，我们只需要确定“第K大的元素”在三个区域的哪一个区域，就能排除另外两个区域了
• 

 使用快速选择算法：

class Solution {
public:int findKthLargest(vector<int>& nums, int k){return qsort(nums, 0, nums.size() - 1, k);}int qsort(vector<int>& nums, int l, int r, int k){if(l == r) return nums[l];//1，随机选择基准元素int a = rand();int key = nums[a % (r - l + 1) + l];//2，根据基准元素将数组排好序并分为三类int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}//3，分情况讨论int c = r - right + 1, b = right - left - 1;if(c >= k) //落在右边区域return qsort(nums, right, r, k);else if(b + c >= k) //落在中间区域return key;else //落在左边区域return qsort(nums, l, left, k - b - c);}
};

 另一种解法，使用优先级队列搞：

class Solution {
public:int findKthLargest(vector<int>& nums, int k){priority_queue<int> p(nums.begin(),nums.end());for(int i=0;i<k-1;i++){p.pop();}return p.top();}
};

 剑指offer 40. 最小的k个数

LCR 159. 库存管理 III - 力扣（LeetCode）

 题目很简单，就是给我们一个数组和一个整数k，找出最小的k个数字，下面我们来分析下这道题：

• 解法一：直接排序，然后找k个最小的数，O(NlogN)
• 解法二：利用堆，我们创建一个大小为k的大堆，然后把数组扔这个堆里去，然后返回 O(NlogK)
• 解法三：快速选择算法，随机选择基准元素，数组分三块，步骤和前面一样
• 

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt){srand(time(nullptr));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() + cnt};}void qsort(vector<int>& nums, int l, int r, int k){if(l >= r) return;//1，选择基准元素int s = rand();int key = nums[s % (r - l + 1) + l];//2，根据基准元素划分数组int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}//3，分情况讨论int a = left - l + 1, b = right - left - 1; //得出左边和中间区域的元素个数if(a > k) qsort(nums, l, left, k);else if(a + b >= k) return;else qsort(nums, right, r, k - a - b);}
};

分治-归并

912. 排序数组

912. 排序数组 - 力扣（LeetCode）

这个题目和上面 “912. 快速排序数组”，的那个题目是一样的，这里只是单纯的复习下归并排序，下面我们来用归并的思想解一下这道题：

• 先来复习下归并排序的基本步骤：
• 
• 当把归并和快排作比较时，可以发现这两个是非常相似的算法，快排就是搞一个基准元素k，然后根据k把数组分成三份，这个和归并是一样的，并且二者都是当分成的数组只剩一个元素时停止分块，所以快排和归并的思想很像，只是处理数组的时机不一样
• 归并排序也很像二叉树的后续遍历（后续遍历就是左右中遍历，把底层搞完再来搞上层）；而快排恰恰相反，先在本层先把数组分成两块，先把本层的搞完，然后再去搞左边，左边搞完后再去搞右边，这就是二叉树前序遍历（中左右）

class Solution {
public:vector<int> tmp;
vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums,0 , nums.size() - 1);return nums;}void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return;//1，先选择中间点，划分区间int mid = (right + left) / 2;//划分好的区间为[left, mid], [mid + 1, right]//2，把左右区间拆分mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);//3，合并小区间，并实现排序int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];else tmp[i++] = nums[cur2++];}//处理还没有遍历完的数组while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//4，还原数组for(int i = left; i <= right; i++)nums[i] = tmp[i - left];}
};

剑指offer 51. 数组中的逆序对

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

题目其实不难看懂，只是有个地方需要注意，就是组成的逆序对中的两个数字的前后顺序是要和原数组对应的，下面来分析下这道题：

•  一般看到这道题最先想到的就是暴力枚举法，而这个题也刚好就是经典的暴力枚举例子，但是不用说，O(N ^ 2)肯定会超时
• 我们来重新搞一个策略，我们把数组分成两部分，然后我们在左边区域挑出来a个逆序对，再去右边挑b个逆序对，然后左边取一个数，右边取一个数，这样“一左一右”挑出来c个逆序对，然后a+b+c的结果也是数组的逆序对（因为这个本质还是暴力枚举，因为每个逆序对的两个数都是挑出来的）
• 再扩展一下上面的策略：左半部分挑完后排个序，右半也一样，两者有序之后，再“一左一右”，这也是正确的，因为左边挑一个再去右边挑的时候，是不管这两个数的顺序的，只需要先从左边挑出来一个数，然后去右边挑比这个数小的就行了；同理，先挑右边的，然后只需要去看看左边有多少个数比我大（左右个自排序不影响“一左一右”的结果）
• 解法：利用归并排序解决。结合归并思想和上面的策略，可以发现“左半部分找逆序对+排序”和“右半部分找逆序对+排序”这两步都是可以在递归中搞的，我们主要的目的就是实现“一左一右 + 排序”
• 策略一：找出该数之前，，有多少个cur1比cur2大
• 

扩展：上面的策略是“找出该数之前，有多少个cur1比cur2大”，所以我们用的升序如果用降序能否解决问题？

• 
• 策略二：找出该数之后，有多少个数比我小，用这个就只能用降序了
• 

策略一，升序： 

class Solution {
public:int tmp[50001] = { 0 };int reversePairs(vector<int>& record) {return mergeSort(record, 00, record.size() - 1);}int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;int ret = 0;//1，找中间点，将数组分成两部分int mid = (left + right) >> 1;//2，分别左右区间的逆序对，并排序ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//3，一左一右的逆序对的个数 —— 策略一：升序int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++]; //完成指针移动和排序功能和归并是一样的}else{ret += mid - cur1 + 1;tmp[i++] = nums[cur2++];}}//4，处理未遍历完的指针while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//5，覆盖原数组for(int j = left;j <= right; j++)nums[j] = tmp[j - left];return ret; //返回逆序对结果数量}
};

策略二，降序：

 其实就改了下24，28和29行

class Solution {
public:int tmp[50001] = { 0 };int reversePairs(vector<int>& record) {return mergeSort(record, 00, record.size() - 1);}int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;int ret = 0;//1，找中间点，将数组分成两部分int mid = (left + right) >> 1;//2，分别左右区间的逆序对，并排序ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//3，一左一右的逆序对的个数 —— 策略一：升序int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur2++]; //完成指针移动和排序功能和归并是一样的}else{ret += right - cur2 + 1;tmp[i++] = nums[cur1++];}}//4，处理未遍历完的指针while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//5，覆盖原数组for(int j = left;j <= right; j++)nums[j] = tmp[j - left];return ret; //返回逆序对结果数量}
};

315. 计算右侧小于当前元素的个数

315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

这个题目和我们上面那个逆序对的题是很相似的，根据示例一就能理解，下面我们来分析下这道题：

• 解法：归并排序（分治)，和上一题一样，把数组分成两半，左右各自找逆序对个数，然后“一左一右”找的话用上一题的策略二：当前元素和后面，有多少个比我小，
• 

• 所以这道题和前面那道题的不同点就是：当我们找到这个元素右边有多少个数比我小的时候，我还要找到这个元素的原始下标（因为我们把数组分成两份之后是排了序的）

• 如何找到排完序后的这个元素的原下标是多少呢？我们搞一个同等大小的数组index，这个数组里存的都是下标。然后两个数组绑定移动：

• 

class Solution 
{vector<int> ret; //返回用vector<int> index; //记录 nums 中各元素的原始下标int tmpNums[500010];int tmpIndex[500010]; //合并数组时的辅助数组
public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);//初始化indexfor(int i = 0; i < n; i++)index[i] = i;mergeSort(nums, 0, n - 1);return ret;}void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return;//1，划分区间int mid = (left + right) / 2;//2，处理左右区间的mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);//3，处理“一左一右”int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){//如果小于就正常归并，如果大于就记录结果if(nums[cur1] <= nums[cur2]) //降序，谁大先移动谁{tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}else //统计结果{ret[index[cur1]] += right - cur2 + 1; //用+=不能用=，因为左右区间算的时候，里面的值已经更新过了，用=的话会覆盖原先的值tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}}//4，处理剩下的排序过程while(cur1 <= mid){tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}//5，还原nums和indexfor(int j = left; j <= right; j++){nums[j] = tmpNums[j - left];index[j] = tmpIndex[j - left];}}
};

493. 翻转对

493. 翻转对 - 力扣（LeetCode）

这个题目可以说就是逆序对的变种，就是把逆序对的“前面大于后面”这个条件变成了“前面大于两倍的后面”，下面我们来分析下这道题：

• 暴力枚举我们就不多说了。因为这个题和逆序对非常相似，所以我们依旧可以按照逆序对的那个策略来分析，解法二：分治
• 老样子把数组分两份，，先求左边和右边的翻转对，再一左一右；逆序对那里是直接将比较大小和归并重合了，就是 nums[i] > nums[j]，但是这道题不一样，这道题是 nums[i] > 2*nums[j]，所以不能按照归并排序的流程求翻转对，我们得重新想一个策略来求
• 我们需要在归并排序之前计算翻转对，因为我们可以利用左右两个数组有序的性质，就可以在一次归并中用O(N)的时间复杂度搞定一堆翻转对个数
• 策略一：计算当前元素后面有多少个元素的两倍比我小，用降序，cur1在left，cur2在mid，cur1先不动，cur2往右移动，当cur2的两倍第一次比cur1小时，cur2后面的就都比cur1小了；但是cur1++后，cur2先别回退，因为此时的cur1是最后一次比cur2大，当cur1++后，cur1就变小了，那么此时cur2的两倍是铁定比cur1大的，所以此时我们的cur2不用退回到mid，直接在现在的位置继续判断即可，ret += right - cur2 + 1; （这个策略就是利用单调性，使用同向双指针）
• 策略二：计算当前元素之前，有多少元素的一半比我大，用升序，也可以利用数组单调性解决问题，cur2不动，如果cur1的一半比cur2大，cur1就继续++，当cur1的一半第一次比cur2小，那么cur1的后面就都比cur2小了，此时ret += mid - cur1 + 1; cur2++; 然后一样的，cur1不必回退到left，而是在当前位置继续判断
• 最后计算完逆序对后，我们还得排序，所以之后还得合并两个数组

策略一，降序：

class Solution
{int tmp[50001];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size() - 1);    }int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;int ret = 0;//1，先划分左右数组int mid = (left + right) / 2;//2，先计算左右两侧的反转对ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//3，计算翻转对的数量int cur1 = left, cur2 = mid + 1, i = left;while(cur1 <= mid){while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;if(cur2 > right) break;ret += right - cur2 + 1; //统计出一左一右的翻转对数量cur1++;}//4，排序cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right) //降序，谁大谁先移{if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur2++];}else{tmp[i++] = nums[cur1++];}}//5，处理剩余的while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//6，合并for(int j = left; j <= right; j++)nums[j] = tmp[j];return ret;}
};

 策略二，升序：

class Solution
{int tmp[50001];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size() - 1);    }int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;int ret = 0;//1，先划分左右数组int mid = (left + right) / 2;//2，先计算左右两侧的反转对ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//3，计算翻转对的数量int cur1 = left, cur2 = mid + 1, i = left;while(cur2 <= right){while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;if(cur1 > mid) break;ret += mid - cur1 + 1; //统计出一左一右的翻转对数量cur2++;}//4，排序cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right) //升序，谁小谁先移{if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++];}else{tmp[i++] = nums[cur2++];}}//5，处理剩余的while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//6，合并for(int j = left; j <= right; j++)nums[j] = tmp[j];return ret;}
};