【基础算法总结】分治--快排+归并

这道题十分经典，它的代码是快速排序的核心代码之一(因为快排有多种实现方式，核心代码也有多种)，它的本质就是数组分三块(数组划分)。
本题是为下面几题做铺垫的，不是用分治算法，而是使用三指针。
(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]);
        }
    }
};

算法原理：

这道题可以使用我们以前学过的快速排序的算法(二路快排)解决，但是当数据中有很多重复值时，使用以前的算法时间复杂度会退化成 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];
    }
};

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];
    }
};

算法原理：

这道题也是一道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];
    }
};

算法原理：

归并排序的大致过程：
先取中间点把数组分为两个区间，要把数组排有序，只要左区间有序，右区间有序了，数组就有序了。所以再递归左区间，取中间点把左区间分又为左右两个区间…一直递归，直到左右区间只剩一个元素不可再分割了，这一层进行回退归并过程，归并的核心就是合并两个有序数组，一直归并到第一层，再进行递归右区间…
图解如下：

细节问题：

这里执行归并操作合并两个有序数组时需要创建临时数组，有两种创建方式：
(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];
    }
};

算法原理：

这道题比较难。在使用归并分治思想解决这个问题前，先来搞定几个铺垫知识：
(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：降序

算法原理：

这题的本质和上一题一样也是计算逆序对的个数，所以也是使用归并分治的思想。
因为这道题是求右侧小于当前元素的个数，所以用的是上一题的策略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];
        }
    }
};

算法原理：

这道题是个逆序对的变式题，但是它不能和 [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：升序