分治

1.颜色分类

解题思路与移动零类似，把数组分为三个部分，一个部分全是0，一个部分全是1，一个部分全是2。移动零的思想是一个指针 i 扫描数组，另一个指针 j 记录符合条件的元素区域的右端，如果nums[i]符合条件，则交换nums[j+1]，j++，i++。

本题则用三指针，把数组划分为4个部分，i 遍历数组，left标记0区域的最右侧，right标记2区域的最左侧。[0,left]全是0，[left+1, i-1]全是1，[i，right-1]待扫描，[right, n-1]全为2。

left初始化为-1，right初始化为n，i从0开始，如果nums[i]==0，则交换nums[left+1]和nums[i]，然后left++，i++；如果nums[i] ==1，则i++；如果nums[i] ==nums[right-1]，则交换两者，right–，i 不动，因为如果nums[right-1]为2，交换后nums[i]就为2，此时nums[i]仍要交换。最后 i 和right相遇时，遍历结束。

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

2.快速排序

这道题可以直接自己写快速排序，用三数取中求下标key，但是过不了，因为当数据量很大且元素都一样的时候，效率会明显退化。

可以用上一道题“颜色分类”的思想，left = -1，right = n，在数组中找到一个元素key，把数组分成 [0，left]小于key，[left+1，i]等于key，[i，right-1]待扫描，[right，n-1]大于key四部分。

最后数组就会被分成[0,left]小于key，[left+1,right-1]等于key，[right,n-1]大于key三部分，再递归处理小于key部分和大于key部分。

如果数组中元素都等于key，只需递归处理两端非法区间，直接返回，此时相当于只遍历了一遍数组，时间复杂度为O(N)，效率更高。

这里不用三数取中求key，从概率论和数学期望的角度，用随机数求key更优。用rand()求得随机数r，再 r%(right-left+1) 得到余数 0 ~ right-left，最后加上left得到正确的下标，所以 key = nums[rand() % (right-left+1) + left]。

class Solution {
public:
    int getKeyRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }
    void QuickSort(vector<int>& nums, int l, int r)
    {
        if (l >= r) //递归终止条件
            return;
        int key = getKeyRandom(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (nums[i] < key)
                swap(nums[i++], nums[++left]);
            else if (nums[i] == key)
                i++;
            else
                swap(nums[i], nums[--right]);
        }
        QuickSort(nums, l, left);
        QuickSort(nums, right, r);
    }
    vector<int> sortArray(vector<int>& nums)
    {
        srand(time(0)); //种下随机数种子
        QuickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

3. 快速选择算法

这种题属于topK问题，有四种类型：求第k大的元素，第k小的元素，前k大的元素，前k小的元素。可以用优先级队列求解，但不符合题目要求的O(N)时间复杂度。

快速选择算法的时间复杂度为O(N)，根据快排的思想，随机数得到元素key，把数组分成<key，==key，>key三部分。a为<key部分的元素个数，b为 ==key部分的元素个数，c为>key部分的元素个数。c>=k，说明第k大的元素在>key部分；否则，如果b+c>=k，说明第k大的元素在 ==key部分，此时直接返回key；前面两者都不符合时，说明第k大的元素在<key部分，此时只要在<key部分找第 k-b-c 大的元素即可。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        srand(time(0));
        return _findKthLargest(nums, k, 0, nums.size() - 1);
    }
    
    int _findKthLargest(vector<int>& nums, int k, int l, int r)
    {
        //数组划分成3部分
        int left = l - 1, right = r + 1, i = l;
        int key = nums[rand() % (r - l + 1) + l];
        while (i < right)
        {
            if (nums[i] < key)
                swap(nums[i++], nums[++left]);
            else if (nums[i] == key)
                i++;
            else
                swap(nums[i], nums[--right]);
        }
        
        int a = left - l + 1, b = (right - 1) - (left + 1) + 1, c = r - right + 1;
        int ret = 0;
        
        //分情况讨论
        if (c >= k)
        {
            ret = _findKthLargest(nums, k, right, r);
            return ret;
        }
        else if (b + c >= k)
            return key;
        else
        {
            ret = _findKthLargest(nums, k - b - c, l, left);
            return ret;
        }
    }
};

4.最小的k个数

此题使用快速选择算法，同时也属于topK问题。解决这道题的思路是用快速选择算法把数组中最小的cnt个元素放到数组前，不考虑其顺序。先用随机数得到key，再根据key把数组分三块，a为<key部分的元素个数，b为==key部分的元素个数。

如果a>cnt，说明此时最小的cnt个元素在<key部分，对该部分用快速选择算法，进一步确定最小的cnt个元素；如果a+b>=cnt，说明最小的cnt个元素在<key 和 ==key 部分，数组中 ==key 部分的每个元素是相同的，所以此时已经把数组stock的最小cnt个元素放在数组前面了，即确定了最小的cnt个元素所在的区间，直接返回。 a == cnt 的情况包含在a+b>=cnt，因为此时最小的cnt个元素就全部在<key部分。

如果两者都不满足，说明<key 和 == key部分都是最小的cnt个元素，并且>key部分还有最小cnt个元素，同样对该部分用快速选择算法，进一步确定。

结果qselect函数，数组stock的前cnt个元素就是最小的，返回这段数组。

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt)
    {
        srand(time(0));
        qselect(stock, cnt, 0, stock.size() - 1);
        return { stock.begin(),stock.begin() + cnt };
    }
    
    //快速选择，使stock的前cnt个元素就是最小的
    void qselect(vector<int>& stock, int cnt, int l, int r)
    {
        if (l >= r)
            return;
        int key = stock[rand() % (r - l + 1) + l];
        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (stock[i] < key)
                swap(stock[i++], stock[++left]);
            else if (stock[i] == key)
                i++;
            else
                swap(stock[i], stock[--right]);
        }
        int a = left - l + 1, b = (right - 1) - (left + 1) + 1;
        if (a > cnt)
            qselect(stock, cnt, l, left);
        else if (a + b >= cnt)
            return;
        else
            qselect(stock, cnt - a - b, right, r);
    }
};

5.归并排序

归并排序即把数组均分成2份，每一部分再均分，直到只剩1个元素，然后借助一个数组合并两个有序数组并回溯。归并排序相当于二叉树的后序遍历，合并两个有序数组的中转数组 t 可作为全局变量或如下所示的类成员，相较于放在MergeSort中，能避免每次递归的消耗。

class Solution
{
    vector<int> t;
public:
    vector<int> sortArray(vector<int>& nums)
    {
        int n = nums.size();
        t.resize(n);
        MergeSort(nums, 0, n - 1);
        return nums;
    }
    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 = 0;
        while (cur1 <= mid && cur2 <= right)
            t[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= mid)
            t[i++] = nums[cur1++];
        while (cur2 <= right)
            t[i++] = nums[cur2++];
		
        //把中转数组t还原到数组nums
        for (i = left;i <= right;i++)
            nums[i] = t[i - left];
    }
};

6.数组中的逆序对

根据题意，逆序对即前面的数比后面的数大。可以暴力枚举，先固定一个数，在数组中往后找比它小的数的个数，显然需要两层循环，时间复杂度为O(N²)。

用分治的策略在时间复杂度上是较优的。把数组分成左右两部分，求出左部分的逆序对数，再求出右部分的逆序对数，最后再左右两边各取一个数比较，得出一左一右的逆序对数，把这三者加起来即为所求逆序对数。时间复杂度仍为O(N²)，但可以结合归并排序优化。

ret记录逆序对个数。那么结合归并排序，数组不断分成两部分，当只剩一个元素时回溯，在合并两个有序数组的同时来求一左一右的逆序对数。在合并时，由于两部分数组是升序的，当record[cur1]>record[cur2]，说明[cur1，mid]的元素全部大于record[cur2]，则ret+=mid-left+1，cur2++。最后ret即为所求。

这种方法时间复杂度为O(NlogN)，并且只需在归并排序的基础上加上ret即可。

class Solution
{
    int t[50010];
public:
    int reversePairs(vector<int>& record)
    {
        return MergeSort(record, 0, record.size() - 1);
    }
    int MergeSort(vector<int>& record, int left, int right)
    {
        if (left >= right)//数组只有一个元素，不会有逆序对。
            return 0;

        int ret = 0;
        int mid = (left + right) >> 1;
        ret += MergeSort(record, left, mid);
        ret += MergeSort(record, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            if (record[cur1] <= record[cur2])
                t[i++] = record[cur1++];
            else
            {
                ret += mid - cur1 + 1;
                t[i++] = record[cur2++];
            }
        }
        while (cur1 <= mid)
            t[i++] = record[cur1++];
        while (cur2 <= right)
            t[i++] = record[cur2++];
        for (i = left;i <= right;i++)
            record[i] = t[i - left];

        return ret;
    }
};

以上是升序的归并排序，使用降序同样可以解决这道题。

如果是降序，对应ret+=cur1-left+1，cur1++，显然这样会重复计算。这时就要从右部分数组考虑，当record[cur1]<=record[cur2]时，由于逆序对要求前大数大，所以cur2++，直到record[cur1]>record[cur2]时，ret+=right-cur2+1，cur1++。

class Solution
{
    int t[50010];
public:
    int reversePairs(vector<int>& record)
    {
        return MergeSort(record, 0, record.size() - 1);
    }
    int MergeSort(vector<int>& record, int left, int right)
    {
        if (left >= right)
            return 0;

        int ret = 0;
        int mid = (left + right) >> 1;
        ret += MergeSort(record, left, mid);
        ret += MergeSort(record, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) //降序版
        {
            if (record[cur1] <= record[cur2])
                t[i++] = record[cur2++]; //
            else
            {
                ret += right - cur2 + 1; //
                t[i++] = record[cur1++]; //
            }
        }
        while (cur1 <= mid)
            t[i++] = record[cur1++];
        while (cur2 <= right)
            t[i++] = record[cur2++];
        for (i = left;i <= right;i++)
            record[i] = t[i - left];

        return ret;
    }
};

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

这道题跟求逆序对数是十分相似的，题目要求返回一个数组，对应位置的元素为nums中每个元素的右侧小于其的元素个数。

降序归并排序，当nums[cur1]<=nums[cur2]时，cur2++，nums[cur2]不是所求。当nums[cur1]>nums[cur2]时，[cur2，right]的元素个数即为所求，则counts[cur1]+=right-cur2+1。

但是，每次回溯时合并有序数组，nums[cur1]、nums[cur2]的位置会发生变化这就导致下标cur1对应的不是nums原来的元素。所以每当nums[cur1]排到前面，下标也要对应变化，创建数组index来记录nums的原始下标。

用中转数组tIndex记录回溯过程中index的变化，再还原到index。最后index[cur1]即对应nums在排序前的下标。

class Solution
{
    vector<int> counts;
    vector<int> index; //记录nums中元素的原始下标
    vector<int> t;
    vector<int> tIndex;//index的中转数组
public:
    vector<int> countSmaller(vector<int>& nums)
    {
        int n = nums.size();
        counts.resize(n);
        index.resize(n);
        for (int i = 0;i < n;i++) //初始化index
            index[i] = i;
        t.resize(n);
        tIndex.resize(n);
        MergeSort(nums, 0, n - 1);
        return counts;
    }
    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 = 0;
        while (cur1 <= mid && cur2 <= right) //降序
        {
            if (nums[cur1] <= nums[cur2])
            {
                t[i] = nums[cur2];
                tIndex[i++] = index[cur2++];
            }
            else
            {
                counts[index[cur1]] += right - cur2 + 1;
                t[i] = nums[cur1];
                tIndex[i++] = index[cur1++];
            }
        }
        while (cur1 <= mid)
        {
            t[i] = nums[cur1];
            tIndex[i++] = index[cur1++];
        }
        while (cur2 <= right)
        {
            t[i] = nums[cur2];
            tIndex[i++] = index[cur2++];
        }
        for (int j = left;j <= right;j++)
        {
            nums[j] = t[j - left];
            index[j] = tIndex[j - left];
        }
    }
};

8.翻转对

本题与逆序对类似，区别是这里要求前面的数比后面的数两倍还大，同样可用升序或降序的方法解决，只要在归并排序的排序部分之前用双指针先计算出符合要求的元素个数即可。

//降序版
class Solution
{
    vector<int> t;
public:
    int reversePairs(vector<int>& nums)
    {
        int n = nums.size();
        t.resize(n);
        return MergeSort(nums, 0, n - 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 = 0;
        while (cur1 <= mid && cur2 <= right) //双指针
        {
            if (nums[cur1] > (long)2 * nums[cur2])//防溢出
            {
                ret += right - cur2 + 1;
                cur1++;
            }
            else
                cur2++;
        }
        cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right)
            t[i++] = nums[cur1] > nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= mid)
            t[i++] = nums[cur1++];
        while (cur2 <= right)
            t[i++] = nums[cur2++];
        for (i = left;i <= right;i++)
            nums[i] = t[i - left];
        return ret;
    }
};

//升序版
class Solution
{
    vector<int> t;
public:
    int reversePairs(vector<int>& nums)
    {
        int n = nums.size();
        t.resize(n);
        return MergeSort(nums, 0, n - 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 = 0;
        while (cur1 <= mid && cur2 <= right) //双指针
        {
            if (nums[cur1] / 2.0 > nums[cur2])
            {
                ret += mid - cur1 + 1;
                cur2++;
            }
            else
                cur1++;
        }
        cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right)
            t[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= mid)
            t[i++] = nums[cur1++];
        while (cur2 <= right)
            t[i++] = nums[cur2++];
        for (i = left;i <= right;i++)
            nums[i] = t[i - left];
        return ret;
    }
};