【算法百题】专题七_分治快排_专题八_分治归并

---

前言

分治顾名思义,就是分而治之,分治是一个思路,并不是由暴力优化而来的,还是因为暴力解的重复比较太多,我们可以将大问题划分为小问题(当然不是无厘头的划分),每次分割后，子问题的规模呈指数级缩小（理想情况下减半），总操作次数从 O(n^2) 降至 O(nlogn).

---

分治快排题：

043. 颜⾊分类（medium）

分析

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

---

044. 快速排序（medium）

分析

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){//3.然后再写"归"的逻辑,如果只有一个值,一个值也是有序的,那么直接返回,不用排了.//if(r - l + 1 == 1) return; 逻辑没错,但是有可能出现l 比 r大的情况if(l >= r) return;//1.这里分治用的是快排的方向,所以先将我们的数组进行划分,然后再递归子区间.int key = getRandNum(nums,l,r);              //随机找一个数作为key,避免有序情况的爆栈int i = l;int left = l - 1,right = r + 1;while(i < right)                                //然后开始将数组根据key值进行划分{if(nums[i] < key) swap(nums[++left],nums[i++]);else if(nums[i] > key) swap(nums[--right],nums[i]);else i++;}//2.递归递归,当然要先写向深处"递"的逻辑.qsort(nums,l,left);qsort(nums,right,r);}int getRandNum(vector<int>& nums,int l,int r){int x = rand();return nums[x % (r - l + 1) + l];}
};

---

045. 快速选择算法（medium）

分析

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(nullptr));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];int key = getRandpm(nums,l,r);int i = l;int left = l - 1,right = r + 1;while(i < right){if(nums[i] < key) swap(nums[++left],nums[i++]);else if(nums[i] > key) swap(nums[--right],nums[i]);else i++;}if(r - right + 1 >= k) return qsort(nums,right,r,k);     //优化再递归思路这里,不用全部递归,可以根据大概的左右子区间的元素个数,判断一下我们的topK最终会在什么区间,时间复杂度是O(N).else if(r - left >= k) return key;else return qsort(nums,l,left,k - (r - left));}int getRandpm(vector<int>& nums,int l,int r){return nums[rand() % (r - l + 1) + l];}
};

---

046. 仓库管理

分析

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>& stock,int l,int r,int cnt){if( l >= r) return;int key = getRandom(stock,l,r);int i = l,left = l - 1,right = r + 1;while(i < right){if(stock[i] < key) swap(stock[++left],stock[i++]);else if(stock[i] > key) swap(stock[--right],stock[i]);else i++;}int a = left - l + 1,b = right - left - 1,c = r - right + 1;  //我们快排本来就是在原数组上面做操作,所以走完逻辑其实原数组也就拍好了if(a >= cnt) qsort(stock, l,left,cnt);else if(a + b >= cnt) return ;else qsort(stock, right,r,cnt - a - b);}int getRandom(vector<int>& stock,int l,int r){return stock[l + rand() % (r - l + 1)];}
};

---

分治归并题

047. 归并排序（medium）

分析

class Solution {vector<int> tmp; //我们合并的过程中,需要一个单独的容器暂时存储.
public: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){//2.然后写"归"的逻辑,不然即使"递"到了最深处,即[l,r]区间的只有一个数据时,也不会停下.if(left >= right) return;    //只有一个数据时,也是有序的.//1.从数组的中间开始划分,先"递"到最深处.int mid = (right + left) >> 1;   mergeSort(nums,left,mid);mergeSort(nums,mid + 1,right);//3.然后开始每个组 合并的逻辑int x = left;int i = left,j = mid + 1;while(i <= mid && j <= right){if(nums[i] <= nums[j]) tmp[x++] = nums[i++];else tmp[x++] = nums[j++];}while(i <= mid)  //如果小组里面还有没合并完的大组,那么,直接放入tmp.{tmp[x++] = nums[i++];}while(j <= right){tmp[x++] = nums[j++];}//将tmp数据同步回原数组,那么我们的一次合并就完成了.for(int i = left;i <= right;i++){nums[i] = tmp[i]; }}
};

---

048. 数组中的逆序对（hard）

分析

class Solution 
{int tmp[50010];
public:int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}int mergeSort(vector<int>& nums,int left,int right){//2.写"归"的逻辑,让它在停在有两个最小组的层.方便我们对两个最小组中的值做刚开始的逆序对判断.if(left >= right) return 0;int ret = 0;//1.先"递"到最小int mid = (left + right) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid + 1,right);//3.合并同时做判断,找到所有符合的逆序对int cur1 = left,cur2 = mid + 1,i = left;while(cur1 <= mid && cur2 <= right){if(nums[cur2] >= nums[cur1]){tmp[i++] = nums[cur1++];}else{ret += mid - cur1 + 1;tmp[i++] = nums[cur2++];}}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//4.将tmp中排序好的顺序数组,覆盖回原数组.for(int i = left;i <= right;i++){nums[i] = tmp[i];}return ret;}
};

---

049. 计算右侧⼩于当前元素的个数（hard）

分析

class Solution {vector<int> ret;vector<int> index;int tmp[100010];int tmpIndex[100010];
public:vector<int> countSmaller(vector<int>& nums){int n = nums.size();ret.resize(n,0);index.resize(n);for(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;int mid = (left + right) >> 1;mergeSort(nums,left,mid);mergeSort(nums,mid + 1,right);int cur1 = left,cur2 = mid + 1,i = left;while(cur1 <= mid && cur2 <= right){if(nums[cur1] > nums[cur2]){ret[index[cur1]] += right - cur2 + 1;tmp[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}else{tmp[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}}while(cur1 <= mid) {tmp[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while(cur2 <= right) {tmp[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}//将临时的下标数组和原数组都同步回去.for(int i = left;i <= right;i++){nums[i] = tmp[i];index[i] = tmpIndex[i];}}
};

---

050. 计算右侧⼩于当前元素的个数（hard）

分析

class Solution {int tmp[50010];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums,0,nums.size() - 1);}int mergeSort(vector<int>& nums,int left,int right){//2."归"if(left >= right) return 0;int ret = 0;//1.先"递"int mid = (left + right) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid + 1,right);//2.1统计所有翻转对.int cur1 = left,cur2 = mid + 1,i = left;while(cur2 <= right){while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) cur1++;if(cur1 > mid) break;ret += mid - cur1 + 1;cur2++;}cur1 = left,cur2 = mid + 1;//3.排序并判断翻转对while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++];}else{tmp[i++] = nums[cur2++];}}//4.将没有排完的排完while(cur1 <= mid){tmp[i++] = nums[cur1++];}while(cur2 <= right){tmp[i++] = nums[cur2++];}//5.将排好的数组覆盖原数组.for(int i = left;i <= right;i++){nums[i] = tmp[i];}return ret;}
};

---

总结

分治的思路,远不止这两种,将问题划分小也不总是针对一个数组的(动规也是分治思想的延伸),但是本专题,针对数组的划分,尽量理解"我们是一名老师,让孩子们站队"的例子.

---

本文章为作者的笔记和心得记录，顺便进行知识分享，有任何错误请评论指点：）。