分治（8题）

目录

一、快排

1.颜色分类

 2.排序数组

3.数组中的第k个最大元素

 4.最小的K个数

二、归并

1. 排序数组

2.数组中的逆序对

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

4.翻转对 

---

一、快排

1.颜色分类

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

        left和right，初始一个初始化为-1，一个初始化为nums.size()。

        i下标左侧是已经遍历过的位置。i位置上的值和left上的值交换时要将i++，因为此时交换过来的值也是已经被交换过的，但是和right位置上的值交换时i不--，因为此时交换过来的值还未检验过。 

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

 2.排序数组

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

        数据有重复的情况下，分三块的效率更高 。在极端情况下，若数组内的值全相同，那么将数组分成两块的快排时间复杂度将会变为O(n的平方)，而分三块的快排则只需要O(n)的时间复杂度

优化:如果我们想要快排的渐进时间复杂度逼近n*logn。我们需要随机选取基准元素，也即下面的

 int getnum(vector<int>& nums, int left , int right)

{ return nums[left + (rand() % (right - left + 1))]; }这个函数

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL));myqsort(nums, 0, nums.size() - 1);//myqsort传进去的是该区间两侧的有效值return nums;}void myqsort(vector<int>& nums, int l , int r){if(l >= r)return;int key = getnum(nums, l, r);int i = l, left = l - 1, right = r + 1;//left和righr定义在最左端往左一格和最右端往右一格while(i < right){if(nums[i] < key){left++;swap(nums[left], nums[i]);//如果nums[i]小于基准值，说明小于基准值的边界可以 //扩展了，而这个边界是left，因此++left后将 //nums[i]和nums[left]这两个位置的数交换i++;}else if(nums[i] == key){i++;}else{right--;swap(nums[right],nums[i]);}}myqsort(nums, l, left);myqsort(nums, right, r);}int getnum(vector<int>& nums, int left , int right){return nums[left + (rand() % (right - left  + 1))];}
};

3.数组中的第k个最大元素

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

class Solution {
public:int mysort(vector<int>& nums, int l, int r, int k){if(l == r)return nums[l];int key = getnum(nums, l, r);int i = l, left = l - 1, right = r + 1;while(i < right){if(key > nums[i]){swap(nums[++left], nums[i++]);//如果}else if( key == nums[i]){i++;}else{swap(nums[--right], nums[i]);}}int c = r - right + 1,b = right - left - 1;if(c >= k){return mysort(nums, right, r, k);}else if(b + c >= k){return key;}else{return mysort(nums , l, left,k -b - c );}}int getnum(vector<int>& nums, int left , int right){return nums[left + (rand() % (right - left  + 1))];}int findKthLargest(vector<int>& nums, int k) {return mysort(nums, 0, nums.size()-1, k);}};

 4.最小的K个数

 面试题 17.14. 最小K个数 - 力扣（LeetCode）

        这题和第三题是几乎一样的，而这种算法之所以快，是因为我们不需要将它们全部排好序。 

class Solution {
public:vector<int> smallestK(vector<int>& arr, int k) {vector<int> ret;if (arr.size() == 0)return ret;srand(time(NULL));MyQuickSelect(arr, 0, arr.size() - 1, k);return { arr.begin(), arr.begin() + k };}void MyQuickSelect(vector<int>& arr, int l, int r, int k){if (l == r)return;int key = getnum(arr, l, r);int i = l, left = l - 1, right = r + 1;while (i < right){if (arr[i] < key){swap(arr[++left], arr[i++]);}else if (arr[i] == key){i++;}else {swap(arr[--right], arr[i]);}}int a = left - l + 1, b = right - left - 1;if (a > k){MyQuickSelect(arr, l, left, k);}else if (a + b >= k){return;}else{MyQuickSelect(arr, right, r, k - a - b);}}int getnum(vector<int>& arr, int l, int r){return arr[l + rand() % (r - l + 1)];}
};

二、归并

1. 排序数组

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

         实际上我们可以把它看成一个二叉树后序遍历。

        我们关注一次过程即可，我们先把左右两边排好，然后把排好的元素一个一个放入临时数组，左右两边合成一块后，再把它覆盖掉原来的数组。

        （由于我们是后续遍历，因此我们首先会把整个数组一直分，直到每个部分只有一个元素，这时候很容易就能把两个只有一个元素的部分合并了，然后再不断向上返回合并）

class Solution {
public:vector<int> tmp;//数组在全局开 会节省很多的时间vector<int> sortArray(vector<int>& nums) {int n = nums.size();tmp.resize(n);mysort(nums, 0, nums.size() - 1);return nums;}void mysort(vector<int> & nums, int l, int r){if(l == r)return;//这里写成l >= r 会更安全 int mid = l + (r - l)/2;mysort(nums, l , mid);mysort(nums, mid + 1, r);int cur1 = l, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= r){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++];}else{tmp[i++] = nums[cur2++];}}while(cur1 <= mid){tmp[i++] = nums[cur1++];}while(cur2 <= r){tmp[i++] = nums[cur2++];}for(int i = l; i <= r; i++){nums[i] = tmp[i-l];}}
};

2.数组中的逆序对

 数组中的逆序对_牛客题霸_牛客网

这题是基于上一题归并排序来做的。 

        要求整个数组的逆序对，我们可以把它划分成两块，先求出这两块内的逆序对组数，然后分别从左右各选出一个组成逆序对。这样就能求出全部的逆序对。在左右两边选择的时候，有两种思路，一种是以右侧某个值为基准，找出左边一大串较大的数，一种是以左边某个值为基础，找出右边一大串较小的数。我们归并排序的两种排序方法（升序和降序）分别对应这两种思路。下面先以升序为例。

        我们联想归并排序的过程。当我们将两个已经排序好的部分内的元素合并时，他们的大小关系有传递性，例如，nums[cur1]右侧的数都比它大，那么当nums[cur1]比nums[cur2]大的时候，这时nums[cur1]右侧所有的元素也就都比nums[cur2]大。那么这样就找出一大串较大值了，它们都以nums[cur2]为右侧较小值。

        而我们只需要在排序的过程中多加一步即可

while(cur1<= mid && cur2 <= r)
        {
            if(nums[cur1] <=  nums[cur2])
            {
                tmp[i++] = nums[cur1++];
            }
            else 
            {
                tmp[i++] = nums[cur2++];
                 ret += mid - cur1 + 1;
            }
        }

 让我们再看看为什么降序的时候不能用这种思路

如图，再升序的情况下我们每次找出左侧较大的数时，会有重复。 

 (用前面我们说过的递归的视角来看的话我们交给这个函数的任务就是，求出这个数组中逆序对的个数并排序）

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型vector * @return int整型*/vector<int> tmp;int InversePairs(vector<int>& nums) {// write code heretmp.resize(nums.size());return mysort(nums, 0, nums.size() - 1)%1000000007;//这里由于题目数据要求，我们要对       //1000000007取余，并且此处和下                                                                                                             //面的取余都必须加，不然会出问题}int mysort(vector<int>& nums, int l, int r){if(l >= r)return 0;int ret = 0;int mid = l + (r - l) / 2;ret += mysort(nums,l, mid);ret += mysort(nums,mid + 1, r);ret %= 1000000007;int cur1 = l, cur2 = mid + 1, i = 0;while(cur1<= mid && cur2 <= r){if(nums[cur1] <=  nums[cur2]){tmp[i++] = nums[cur1++];}else //nums[cur1] >  nums[cur2]{tmp[i++] = nums[cur2++];ret += mid - cur1 + 1;}}while(cur1 <= mid)tmp[i++] = nums[cur1++];while(cur2 <= r)tmp[i++] = nums[cur2++];for(int i = l; i <= r; i++){nums[i] = tmp[i-l];}return ret;}
};

 这里是第二种方法的代码，只需要修改一点点。

while(cur1<= mid && cur2 <= r){if(nums[cur1] >=  nums[cur2]){tmp[i++] = nums[cur1++];ret += r - cur2 + 1;}else {tmp[i++] = nums[cur2++];}}

        可以理解为，当你找到一个较大的nums[cur1]时，如果是升序排序，那么就从左边数组找一串较大的。

        如果是降序排序，那么就从右侧找一串较小的

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

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

        宏观来看，我们用一个递归（即归并排序的逻辑），交给我们这个函数的任务是，计算当前数组中每个位置右侧小于当前元素的个数并排序。

         那么我们的整体逻辑就有了，我们要计算一整个数组，第一步可以把它分成两块，分别算算左右两个数组中每个位置右侧小于当前元素的个数，第二步再分别算算以左侧数组中的每个元素为基准，右侧数组中有多少个元素小于这个元素，加上即可。由于我们归并排序在，因此算第二步的时候会容易很多，可以一次性算出很多个。

        题目要求我们返回一个count数组，counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。由于我们需要给nums数组排序，所以我们必须再建一个indexarr数组，用于绑定每个数和它的下标。

        我们的nums数组在归并时需要一个临时数组，因此理所当然indexarr数组也需要一个临时数组。

 

         由上面我们可以看出，在归并时，nums[cur1] 和nums[cur2]的值是元素本身，

        而index[cur1] 和index[cur2]是该元素对应下标的值。我们count中每个下标对应的都是nums中元素未经过排序的原始下标，而index中存的也是原始下标

        所以我们这样加即可，count[indexarr[cur1]] += r - cur2 + 1;//这里是最重要的地方

        因为我们的条件判断是 nums[cur1] > nums[cur2]，因此我们是count[indexarr[cur1]]加上对应的值。

class Solution {
public:vector<int> tmparr;//nums的辅助数组vector<int> indexarr;vector<int> tmpindexarr;//indexarr的辅助数组vector<int> count;vector<int> countSmaller(vector<int>& nums) {int n = nums.size();tmparr.resize(n);indexarr.resize(n);tmpindexarr.resize(n);count.resize(n);for(int i = 0; i < n; i++)indexarr[i] = i;mysort(nums, 0, n-1);return count;}void mysort(vector<int> & nums, int l, int r){if(l >= r)return;//1.求中间值，数组分块int mid = l + (r - l)/2;//2.处理左右两部分mysort(nums, l, mid);mysort(nums, mid + 1, r);//3.归并逻辑，同时处理一左一右的情况int cur1 = l, cur2= mid + 1, i = 0;while(cur1 <= mid && cur2 <= r){if(nums[cur1] > nums[cur2]){tmpindexarr[i] = indexarr[cur1];tmparr[i] = nums[cur1];count[indexarr[cur1]] += r - cur2 + 1;//这里是最重要的地方i++;cur1++;}else{tmpindexarr[i] = indexarr[cur2];tmparr[i] = nums[cur2];i++;cur2++;}} while(cur1 <= mid){tmpindexarr[i] = indexarr[cur1];tmparr[i++] = nums[cur1++];}while(cur2 <= r){tmpindexarr[i] = indexarr[cur2];tmparr[i++] = nums[cur2++];}for(int j = l; j <= r; j++){nums[j] = tmparr[j - l];indexarr[j] = tmpindexarr[j - l];}}
};

4.翻转对 

493. 翻转对 - 力扣（LeetCode） 

这个题就是逆序对的变种题，只是将判断条件改为 一个大于另一个数的两倍。

所以这道题唯一不同的是，我们需要事先统计翻转对，不能将翻转对的统计和合并一起做了。

我们如果没找到合适的nums[cur1]，我们需要将cur1一直++。

while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) { cur1++; }

因此不能把翻转对的统计和数组的合并放在一起

class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& nums) {tmp.resize(nums.size());return mysort(nums, 0, nums.size()-1);}int mysort(vector<int>& nums, int l, int r){int ret = 0;if(l >= r)return 0;int mid = l + (r - l)/2;ret += mysort(nums, l, mid);ret += mysort(nums, mid + 1, r);int i = 0, cur1 = l, cur2 = mid + 1;while(cur2 <= r){while(cur1 <= mid && nums[cur1] / 2.0 <=  nums[cur2]){cur1++;}if(cur1 > mid)break;ret += mid - cur1 + 1;cur2++;}cur1 = l;cur2 = mid + 1;while(cur1 <= mid && cur2 <= r){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++];}else{tmp[i++] = nums[cur2++];}}while(cur1 <= mid){tmp[i++] = nums[cur1++];}while(cur2 <= r){tmp[i++] = nums[cur2++];}for(int i = l; i <= r; i++){nums[i] = tmp[i - l];}return ret;}
};