Leetcode.315. 计算右侧小于当前元素的个数 归并排序（分治）_【分治】右边小于当前元素的数的个数

题目：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

题目要求的就是关于当前元素大于右边元素，比如：5 3 2 4 对于5来说，3 2 4都是可以与5组成逆序对，其实就是求逆序数。

逆序数：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

求逆序数可以根据归并排序时，顺带着求出个数。
比如我们排序好了两个子区间：
左区间：【2，4，6，7】
右区间：【3，5，8，9】
我们归并排序时先取2，对于2，右区间没有小于它的；再取3，再取4时，这时右区间指的是5（下标为5），这时我们元素4就有1个逆序数了，因此，在归并排序两个有序子区间时，我们可以顺带着记录下逆序数的个数

这个可以使用分治递归的思想，在我们求一个子区间【left,right】的对于元素A，右边有多少数小于A的后，排序后都变到A的左边了。
排序完我们就得到了总的逆序数。

对于这道题来说，它要的是每个元素的逆序数，因此，我们要用一个index数组来记录下标。 我们排序就是下标在变，原数组不变。
5 3 2 4 （0，1，2，3）-》2 3 4 5（2，1，3，0）

class Solution {
    int[] count,temp,index;
    int n;
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> ans=new LinkedList();
        n=nums.length;
        if(n==0)    return ans;
        count=new int[n];
        temp=new int[n];
        index=new int[n];
        for(int i=0;i<n;i++)
            index[i]=i;
        merge(nums,0,n-1);
        for(int i=0;i<n;i++)
            ans.add(count[i]);
        return ans;
    }
    void merge(int[] nums,int l,int r){
        if(l==r)    return;
        int mid=(l+r)/2;
        merge(nums,l,mid);
        merge(nums,mid+1,r);
        //左区间最后一个数大于右区间第一个数，整个序列是排好的，没有逆序数了
        if(nums[index[mid]]>nums[index[mid+1]])
            mergeTwo(nums,l,mid,r);
    }
    void mergeTwo(int[] nums,int left,int mid,int right){
    	//temp为索引原数组，index为排好序的数组
        for(int i=left;i<=right;i++)
            temp[i]=index[i];
       	//i为左区间的指针,j为右区间的指针
        int i=left,j=mid+1;
        //k从左到右记录排好序的index
        for(int k=left;k<=right;k++){
        	//如果左边都排好了，右边的补上
            if(i>mid)
                index[k]=temp[j++];
            //如果右边都排好了，那当前元素就有右边整个区间个数的逆序数
            else if(j>right){
                index[k]=temp[i++];
                count[index[k]]+=right-mid;
            }
            //左右区间都有剩,左边的小，要拿出来了，所以当前这个小的元素就有（j-mid-1）个逆序数
            else if(nums[temp[i]]<=nums[temp[j]]){
                index[k]=temp[i++];
                count[index[k]]+=j-mid-1;
            }
            //右边的小，补上
            else
                index[k]=temp[j++];
        }
    }
}
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