算法笔记（五）——分治

算法笔记（五）——分治

分治算法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)…

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

步骤

• 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
• 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
• 合并：将各个子问题的解合并为原问题的解

经典的分治算法有二分搜索，归并排序，快速排序，。

快排

颜色分类

题目：颜色分类

思路

• 初始化三个指针：
• i遍历数组；
• left左侧均为0
• right右侧均为2
• 遍历过程中遇到0，swap(nums[++left],nums[i++])
• 遇到1，i++，不进行交换
• 遇到2，swap(nums[--right], nums[i])
• 循环条件i < right

C++代码

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

排序数组

题目：排序数组

思路

• 我们将数组划分为三块，再来实现快排，将数组划分为三个部分：小于、等于、大于基准值；
• <key，=key，>key

三路划分：减少重复元素的递归处理（相同元素过多的话，可以减小递归深度）、避免不必要的交换（将相同元素聚集在一起，避免了不必要的交换操作）

C++代码

class Solution 
{
public:int getKey(vector<int>& nums, int left, int right){return nums[rand() % (right - left + 1) + left];}void qsort(vector<int>& nums, int l, int r){if(l >= r) return;int key = getKey(nums, l, r);int i = l, left = l - 1, right = r + 1;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}qsort(nums, l, left);qsort(nums, right, r);}vector<int> sortArray(vector<int>& nums) {srand(time(NULL));qsort(nums, 0, nums.size() - 1);return nums;}
};

数组中的第K个最大元素

题目：数组中的第K个最大元素

思路

常规解法，利用堆排，但时间复杂度不为O(N)

快速选择算法（快排）O(N)

• 三路划分，将数组划分为三块；
• 大于key的元素个数为c，等于key的元素个数为b，小于key元素个数为a
• 若 c >= k，则第k大元素在右侧，继续在右侧递归寻找第k大元素；
• 若b + c >= k，则直接返回基准元素，即为第k大元素；
• 若上述均不满足，则第k大元素在左侧，继续在左侧递归寻找第k大元素，此时k = k - b - c

C++代码

class Solution 
{
public:// 数组中获得随机值 int getKey(vector<int>& nums, int l, int r) {return nums[rand() % (r - l + 1) + l];}int qsort(vector<int>& nums, int l, int r, int k){if(l == r) return nums[l];// 随机选择基准元素int key = getKey(nums, l, r);// 根据基准元素将数组分为三块int i = l, left = l - 1, right = r + 1;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}int b = right - 1 - (left + 1) + 1; // 等于key的数量int c = r - right + 1; // 大于key的数量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);}int findKthLargest(vector<int>& nums, int k)             {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}
};

库存管理 III

题目：库存管理 III

思路

和上题想法一致，使用快速选择的算法，使时间复杂度达到O(n)

C++代码

```class Solution 
{
public:void qsort(vector<int>& nums, int l, int r, int cnt){if(l >= r) return ;int key = nums[rand() % (r - l + 1) + l];int i = l, left = l - 1, right = r + 1;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}int a = left - l + 1;int b = right - 1 - (left + 1) + 1;if(a >= cnt) qsort(nums, l, left, cnt);else if((a + b) >= cnt) return;else qsort(nums, right, r, cnt - a - b);}vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() + cnt};}
};

归并

排序数组

题目：排序数组

C++代码

class Solution 
{// 归并vector<int> tmp;
public:void mergeSort(vector<int>& nums, int l, int r){if(l >= r) return ;// 计算中间位置int mid = (l + r) >> 1;// 对左右两部分进行归并排序mergeSort(nums, l, mid);mergeSort(nums, mid + 1, r);// 归并合并两个有序部分int i = l, j = mid + 1, k = 0;while(i <= mid && j <= r)tmp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];while(i <= mid) tmp[k++] = nums[i++];while(j <= r) tmp[k++] = nums[j++];// 拷贝回原数组for(int i = l; i <= r; i++){nums[i] = tmp[i - l];}} vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums, 0, (int)nums.size() - 1);return nums;}
};

交易逆序对的总数

题目：交易逆序对的总数

思路
当我们将两个已排序的子数组合并成一个有序数组时，如果左侧子数组中的某个元素大于右侧子数组中的某个元素，那么左侧子数组中该元素之后的所有元素（包括该元素本身）都将与右侧子数组中的该元素形成逆序对。因此，我们可以通过计算这样的元素对数来统计逆序对的总数

C++代码

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){if(left >= right) return 0; int ret = 0;// 中间，将数组分为两部分int mid = left + right >> 1;// [left, mid], [mid + 1, right]// 左边个数 + 排序 + 右边个数 + 排序ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);// 一左一右个数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++];                }}// 处理剩余元素while (cur1 <= mid) tmp[i++] = nums[cur1++];while (cur2 <= right) tmp[i++] = nums[cur2++];// 拷贝回原数组for (int i = left; i <= right; ++i)nums[i] = tmp[i - left];return ret;}
};

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

题目：计算右侧小于当前元素的个数

思路

这⼀道题的解法与求数组中的逆序对的解法是类似的，记录每⼀个元素的右边有多少个元素⽐⾃⼰⼩

归并排序的过程中，元素的下标是会跟着变化的，因此我们需要⼀个辅助数组，来将数组元素和对应的下标绑定在⼀起归并，也就是再归并元素的时候，顺势将下标也转移到对应的位置上

C++代码

class Solution 
{vector<int> ret;vector<int> index; // 记录当前元素的元素下标int tmpNums[500010];int tmpIndex[500010];
public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);  index.resize(n);// 初始化tmpIndexfor(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;// [left, mid]、[mid + 1, right]// 处理左右两部分mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 处理一左一右，降序数组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++];  }}    // 处理剩余数组while(cur1 <= mid){tmpNums[i] = nums[cur1];tmpIndex[i++]=index[cur1++];}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndex[i++]=index[cur2++];}// 还原for(int j = left; j <= right; j++){nums[j] = tmpNums[j - left];index[j] = tmpIndex[j - left];}}
};

翻转对

题目：翻转对

思路

翻转对和逆序对的定义⼤同⼩异，逆序对是前⾯的数要⼤于后⾯的数。⽽翻转对是前⾯的⼀个数要⼤于后⾯某个数的两倍。因此，我们依旧可以⽤归并排序的思想来解决这个问题

C++代码

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){if(left >= right) return 0;int ret = 0;int mid = (left + right) >> 1;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);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++;}cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int j = left; j <= right; j++)nums[j] = tmp[j];return ret;}
};