LeetCode-315.计算右侧小于当前元素的个数、归并排序_leetcode 315

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质：counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。示例: 输入: [5,2,6,1] 输出: [2,1,1,0]
力扣（LeetCode）第315题

归并排序

将两个有序的数组合并成一个有序数组称为归并。归并排序包含了两个过程：
  ①：从上往下的分解：把当前区间一分为二，直至分解为若干个长度为1的子数组
  ②：从下往上的合并：两个有序的子区域两两向上合并
  如下图所示：

归并排序的一般步骤：
①．分解：把当前区间一分为二，分解点即中间点mid = (left+right)/2
②．求解：分别递归左右两个子区间[left…mid] 和 [mid+1…right]进行归并排序。递归的终结条件是子区间长度为1。
③．合并：把两个有序子数组合并需要占用一个临时空间，依次挪动两个子区间的指针，比较元素值大小，将较小的值存入临时空间的开头。将两个有序区间归并成一个临时有序区间[left…right]，并将结果拷贝到原数组的区间[left…right]，使原始数组[left…right]变为有序。

过程分析

当合并左右两个有序区间时，分为以下几种情况：
①．“左区间”、“右区间”都还有元素，当前右区间元素值小时

如上图，右区间中元素 j 小于左区间中元素 i，则元素 j 小于左区间中范围 [i,mid] 中的所有元素。
②．“左区间”元素用完、“右区间”还剩有元素时

如上图，左区间中元素已经排完，此时右区间中还剩余有元素，此时右区间中元素值全部大于左区间中元素值。
③．“右区间”元素用完、“左区间”还剩有元素时

如上图，右区间中元素已经排完，此时左区间中还剩余有元素，此时左区间中元素值全部大于右区间中元素值。

索引数组

题目中要求的对每个位置求右侧小于改位置的数组的元素个数，若直接对原数组按数值进行排序，则排序后各元素的位置发生变动，无法和原数组中位置进行对应。
因此可以用原数组的索引值建立新数组，排序时根据索引值获取对应数值进行比较，可以只让索引参与排序。

代码示例

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size(),0);//保存结果
        vector<int> indexs(nums.size(),0);//索引数组
        for(int i = 0;i < indexs.size();i++)//索引赋值
        {
            indexs[i] = i;
        }
        vector<int> tempindexs(indexs.size(),0);//临时数组
        mergeSort(nums,indexs,tempindexs,res,0,nums.size()-1);
        return res;
    }
    void mergeSort(vector<int>& nums,vector<int>& indexs,vector<int>& tempindexs,vector<int>& res,int left,int right)
{
        if( left >= right ) return;
        int mid = left + (right - left) /2 ;
        mergeSort(nums,indexs,tempindexs,res,left,mid);//前有序数组
        mergeSort(nums,indexs,tempindexs,res,mid+1,right);//后有序数组
        int i = left;
        int j = mid+1;
        int t = 0;
        while( i <= mid && j <= right )
        {
            if( nums[indexs[i]] > nums[indexs[j]] ) // 则 j 对应的数，小于从 i 开始的所有数据
            {
                for( int k = i;k <= mid ;k++)
                {
                    res[indexs[k]] ++;
                }
                tempindexs[t++] = indexs[j++];
            }
            else
            {
                tempindexs[t++] = indexs[i++];
            }
        }
        while( i <= mid )
        {
             tempindexs[t++] = indexs[i++];
        }
        while( j <= right )
        {
            tempindexs[t++] = indexs[j++];
        }
        t  = 0 ;
        while( left <= right )
        {
            indexs[left++] = tempindexs[t++];
        } 
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53