题解 | #右侧更小数#

利用归并排序，逆序对出现，记录结果

import java.util.*;


public class Solution {
    public class Info{
        private int v;//对应原来数组的值
        private int i;//对应原来数组的下标
        public Info(int value,int index){
            v = value;
            i = index;
        }

    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型ArrayList
     * @return int整型ArrayList
     */
    public ArrayList<Integer> smallerCount (ArrayList<Integer> nums) {
        // write code here
        // int[] arr = nums.stream().mapToInt(Integer::intValue).toArray();
        Info [] arr = new Info[nums.size()];
        ArrayList<Integer>  ans = new ArrayList<Integer> (nums.size());
        for(int i = 0;i<nums.size();i++){
            arr[i] = new Info(nums.get(i),i);
            ans.add(0);
        }
        
        process(arr,0,nums.size() -1,ans);
        return ans;
    }

    public void process(Info[] arr,int L,int R,ArrayList<Integer> ans){
        if(L == R){
            return;
        }
        int mid  = (L +R) /2;
        process(arr,L,mid,ans);
        process(arr,mid+1,R,ans);
        merge(arr,L,mid,R,ans);
    }

    public void merge(Info [] arr,int L,int mid,int R,ArrayList<Integer> ans){
        Info [] help = new Info[R - L+1];
        int index = help.length -1;
        int p1 = mid;
        int p2 = R;

        while(p1 >= L && p2 > mid){
            if(arr[p1].v > arr[p2].v){
                ans.set(arr[p1].i, ans.get(arr[p1].i) + (p2 - mid));
            }
            help[index--] = arr[p1].v > arr[p2].v ? arr[p1--] : arr[p2--];
        }

        while( p1>= L){
            help[index--] = arr[p1--];
        }
        while(p2 > mid){
            help[index--] = arr[p2--];
        }
        
        for(int i = 0;i< help.length;i++){
            arr[L +i] = help[i];
        }
    }
    
}

}

public class Solution {

public class Info{

private int v;//对应原来数组的值

private int i;//对应原来数组的下标

public Info(int value,int index){

v = value;

i = index;

}

}

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

*

* @param nums int整型ArrayList

* @return int整型ArrayList

*/

public ArrayList<Integer> smallerCount (ArrayList<Integer> nums) {

// write code here

// int[] arr = nums.stream().mapToInt(Integer::intValue).toArray();

Info [] arr = new Info[nums.size()];

ArrayList<Integer> ans = new ArrayList<Integer> (nums.size());

for(int i = 0;i<nums.size();i++){

arr[i] = new Info(nums.get(i),i);

ans.add(0);

}

process(arr,0,nums.size() -1,ans);

return ans;

}

public void process(Info[] arr,int L,int R,ArrayList<Integer> ans){

if(L == R){

return;

}

int mid = (L +R) /2;

process(arr,L,mid,ans);

process(arr,mid+1,R,ans);

merge(arr,L,mid,R,ans);

}

public void merge(Info [] arr,int L,int mid,int R,ArrayList<Integer> ans){

Info [] help = new Info[R - L+1];

int index = help.length -1;

int p1 = mid;

int p2 = R;

while(p1 >= L && p2 > mid){

if(arr[p1].v > arr[p2].v){

ans.set(arr[p1].i, ans.get(arr[p1].i) + (p2 - mid));

}

help[index--] = arr[p1].v > arr[p2].v ? arr[p1--] : arr[p2--];

}

while( p1>= L){

help[index--] = arr[p1--];

}

while(p2 > mid){

help[index--] = arr[p2--];

}

for(int i = 0;i< help.length;i++){

arr[L +i] = help[i];

}

}

}