【基础算法总结】分治--快排+归并
目录
- 一，分治算法介绍
- 二，算法原理和代码实现
- 75.颜色划分
- 912.排序数组-快速排序
- 215.数组中的第k个最大元素(快速选择算法)
- LCR159.最小的k个数(快速选择算法)
- 912.排序数组-归并排序
- LCR170.数组中的逆序对
- 315.计算右侧小于当前元素的个数
- 493.翻转对
- 三，算法总结
一，分治算法介绍
分治是一类十分重要的算法，"分治"顾名思义就是分而治之，把一个大问题分成若干个相同或是相似的子问题 ，再把这些小问题继续划分成若干个相同或是相似的更小子问题…直到最小子问题不可再划分。接着通过解决最小子问题进而解决了上一层更小子问题…又进而解决了大问题。这个过程就是 – 递归。
我们学过的快速排序和归并排序就是非常典型也是非常重要的分治。但是它们的分治思想不仅仅用于排序上，在解决其他问题时也是非常有效的。下面介绍的若干道题目就是使用快排和归并的核心思想解决的，让大家加深对它们的理解。
二，算法原理和代码实现
75.颜色划分
这道题十分经典，它的代码是快速排序的核心代码之一(因为快排有多种实现方式，核心代码也有多种)，它的本质就是数组分三块(数组划分)。
本题是为下面几题做铺垫的，不是用分治算法，而是使用三指针。
(1) 首先是三个指针的作用：
i：遍历扫描数组，初始化为0
left：标记0区域的最右侧，初始化为-1
right：标记2区域的最左侧，初始化为最后一个元素的下一个位置。
(2) 这三个下标把数组分为4部分：
[0,left] ：全是0
[left+1,i-1]：全是1
[i,right-1]：待扫描的元素
[right, n-1]：全是2
(3) 在扫描过程中：
a. 当arr[i] == 0时：swap(arr[++left],arr[i++])，把0放入指定区域，并完成指针移动
b. 当arr[i] == 1时：i++
c. 当arr[i] == 2时：swap(arr[–right],arr[i])，把2放入指定区域，但是i不能移动，因为交换后 i 所指的依旧是待扫描的。
(4) 当 i 与 right 相遇后，待扫描区间不存在了，此时遍历结束。
代码实现：
class Solution
{
public:
void sortColors(vector<int>& nums)
{
int n = nums.size();
int left = -1, right = n, i = 0;
// 当i >= right时，说明待扫描区域已经扫描完了，可以结束了
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.排序数组-快速排序
算法原理：
这道题可以使用我们以前学过的快速排序的算法(二路快排)解决，但是当数据中有很多重复值时，使用以前的算法时间复杂度会退化成 O(N^2)。
我们上一题介绍的"数组分三块"(三路快排)的思想就可以很好的解决这个问题，原因是当数组里的数据都是 key 时，进行一次划分后就变成一块区域了(就是等于key的，没有大于或是小于key的)，此时没有左右区间，就不用进行递归了，直接结束。这里的时间复杂度是 O(N) 级别。
这里还可以进行优化：用随机的方式选择基准元素。
代码实现：
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
srand(time(NULL)); // 种随机数种子
qsort(nums, 0, nums.size()-1);
return nums;
}
void qsort(vector<int>& nums, int l, int r)
{
if(l >= r) return;
// 数组分三块(三路快排)
int key = getRandom(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]);
}
// 走完一遍"数组分三块"时，i与right已经重合了
// [l, left] [left+1, right-1] [right, r]
qsort(nums, l, left);
qsort(nums, right, r);
}
int getRandom(vector<int>& nums, int left, int right)
{
int r = rand();
return nums[r % (right - left + 1) + left];
}
};
215.数组中的第k个最大元素(快速选择算法)
topK问题是一类很重要的问题，一般有4种问法：
a. 找第K大
b. 找第K小
c. 找前K大
d. 找前K小
解决这类问题有两种算法：
(1) 堆结构 – O(N * logN)
(2) 快速选择算法(基于快排) – O(N)
算法原理：
这道题是基于上一题的快排算法内容，由前文可知，基准值 key 把数组分为三块区域，从左往右依次是小于key，等于key，大于key。所以我们只需要确定本题中要找的的第 k 大元素落在哪个区域，就在哪块区域里找，其余两块区域不需要再考虑了。
所以接下来的重点就是要讨论如何确定第 k 大元素落在哪个区域？
假设数组中的三块区域的元素的个数分别是 a，b，c。分三种情况讨论：
(1) 如果是落在最右边的区域，则 c >= k。
此时只需要去 [right, r] 区域，继续找第 k 大元素就好了。
(2) 如果是落在中间的区域，则 b+c >= k。
此时第 k 大元素一定是在中间的区域，直接返回 key 即可。
(3) 如果(1)(2)都不成立，此时要去 [l, left] 区域，找第 k-b-c 大的元素。
代码实现：
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
srand(time(NULL));
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 = getRandom(nums, l, r);
// 数组分三块
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]);
}
// 分情况讨论
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);
}
int getRandom(vector<int>& nums, int left, int right)
{
return nums[rand() % (right - left + 1) + left];
}
};
LCR159.最小的k个数(快速选择算法)
算法原理：
这道题也是一道topk问题，解法也有多种：一是直接排序，再取出前k个元素，时间复杂度O(N * ogN)，二是使用堆结构，时间复杂度O(N * logN)，三是使用快速选择算法，时间复杂度O(N)。
这里只介绍快速选择算法。本题的算法原理和上一题基本上是一模一样的，此处不再详细分析了。简略分析如下：
细节问题：
根据算法原理可知，快速选择完之后，我们并没有把数组排序，只是把最小的k个数扔到了数组前面，数组还是无序的。
代码实现：
class Solution
{
public:
vector<int> inventoryManagement(vector<int>& stock, int cnt)
{
srand(time(NULL));
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;
// 在数组里找随机值做key
int key = getRandom(nums, l, r);
// 数组分三块
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]);
}
// 分情况讨论
// [l, left] [left+1, right-1] [right, r]
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);
}
int getRandom(vector<int>& nums, int left, int right)
{
return nums[rand() % (right - left + 1) + left];
}
};
912.排序数组-归并排序
算法原理：
归并排序的大致过程：
先取中间点把数组分为两个区间，要把数组排有序，只要左区间有序，右区间有序了，数组就有序了。所以再递归左区间，取中间点把左区间分又为左右两个区间…一直递归，直到左右区间只剩一个元素不可再分割了，这一层进行回退归并过程，归并的核心就是合并两个有序数组，一直归并到第一层，再进行递归右区间…
图解如下：
细节问题：
这里执行归并操作合并两个有序数组时需要创建临时数组，有两种创建方式：
(1) 边递归边创建
(2) 提前创建好，并且开好空间(推荐)
代码实现：
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)
{
if(left >= right) return;
// 找中间点
int mid = (right + left ) / 2;
//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)
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : 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];
}
};
LCR170.数组中的逆序对
算法原理：
这道题比较难。在使用归并分治思想解决这个问题前，先来搞定几个铺垫知识：
(1) 总对数 = 左半区间逆序对个数a + 右半区间逆序对个数b + 左选一个右选一个组成的逆序对个数c。
再对第一个知识进行延伸：
(2) 在左半区间找出逆序对个数a后，进行排序，右半区间找出逆序对个数b后，也进行排序，最后再左选一个右选一个组成的逆序对个数c，也跟着排序，此时 a + b + c = 总对数。
有了上面两点铺垫知识，就可以引出归并排序的算法了：
把整个数组按中点分成两部分，可以在递归中完成左右两区间逆序对个数的计算，同时进行排序，核心过程是如何计算左选一个右选一个组成的逆序对个数，加排序？如果数组有序，可以统计出一大堆。
策略1：用升序，找到该数之前，有多少个数比我大。盯着 cur2 看。
此时是在归并过程中，已经定义了 cur1 和 cur2，分情况讨论：
(1) nums[cur1] <= nums[cur2] -> 此时不能确定左边有多少个数比 nums[cur2]大，cur1++。
(2) nums[cur1] > nums[cur2] -> ret += (mid - cur1 + 1) 个对，一次统计出来一堆，再 cur2++。
拓展内容：
策略1中，能否用降序，找到该数之前，有多少个数比我大。也盯着 cur2 看？ 不可行。
原因：此时在归并过程中，[left, cur1-1] 区间的数都比 nums[cur1] 要大，[mid+1, cur2-1] 区间的数都比 nums[cur2] 要大，如果我们计算 cur1-1 - left +1 的个数，那在 cur1++ 后又要重新计算前面的个数了。
策略2 ：用降序，找到该数之后，有多少个数比我小。盯着 cur1 看
(1) nums[cur1] <= nums[cur2] -> 此时不能确定左边有多少个数比nums[cur2]小，cur2++。
(2) nums[cur1] > nums[cur2] -> ret += (right - cur2 + 1)个对，一次统计出来一堆，再 cur1++。
代码实现：
这里用的是策略1的升序。
class Solution
{
vector<int> tmp;
public:
int reversePairs(vector<int>& nums)
{
tmp.resize(nums.size());
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;
// 左边的个数+排序 右边的个数+排序
// [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 j = left; j <= right; j++)
nums[j] = tmp[j-left];
return ret;
}
};
策略1和策略2的代码差异：
策略1：升序
策略2：降序
315.计算右侧小于当前元素的个数
算法原理：
这题的本质和上一题一样也是计算逆序对的个数，所以也是使用归并分治的思想。
因为这道题是求右侧小于当前元素的个数，所以用的是上一题的策略2降序。
但是这道题与上一题不同的是：
我们统计出个数之后，不是直接 ret+= 返回，而是要把个数存入另一个数组的和这个元素对应(原始下标)的位置上。
所以这里我们还要解决一个问题就是：
当统计出 nums[cur1] 的后面有多少个元素比它小之后，还要能找到这个元素的原始下标(在递归过程中cur1是会移动的)。
解决方法：
搞一个与原数组nums同规模的 index 数组，里面的值存的是原数组中每个元素的下标。然后不管nums数组里的元素怎么移动，index 数组里面的值都与它绑定一起移动。
代码实现：
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);
// 记录原始下标
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;
// [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];
}
}
};
493.翻转对
算法原理：
这道题是个逆序对的变式题，但是它不能和 [LCR170.数组中的逆序对] 一样在归并过程中统计翻转对的个数。因为在那道题中的 nums[i] > nums[j] 与归并过程比较时(合并两个有序数组)是一样的，但是这道题的比较是 nums[i] > 2 * nums[j]，与归并过程比较时不同。
解决方法就是：
要在归并过程之前计算翻转对的个数。因为我们要利用这两个数组有序的特性：
策略1：计算当前元素后面，有多少元素的两倍比我小，此时降序
此时让 cur1 和 cur2 指向两个区间的开始，盯着 cur1 的元素，先固定cur1不动：
(1) 若 nums[cur1] <= 2 * nums[cur2]，由于是降序数组，只有 cur2向后移时，才能让nums[cur1] > 2 * nums[cur2]
(2) cur2++，直到 nums[cur1] > 2 * nums[cur2] ，此时 ret += right - cur2 + 1
(3) 再让cur1++，注意此时 cur2 还是一直往后走
(4) 直到 cur1 或 cur2 走出区间
策略2：计算当前元素之前，有多少元素的一半比我大，此时升序
代码实现：
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 mid = (left + right) >> 1;
// [left, mid] [mid+1, right]
int ret = 0;
// 计算左右区间的个数
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;
}
};
策略1和策略2的代码差异：
策略1：降序
策略2：升序
三，算法总结
上面的若干道题都是基于快排和归并的思想解决的，所以最重要的还是要理解这两种排序算法。
如果想要更加详细的学习两种排序算法，请点击下面两篇文章：
(1) 归并排序和计数排序
(2) 快速排序和冒泡排序