P11-SmallerNumbers/SolutionJava.java at main · TheQueryCrew/P11-SmallerNumbers · GitHub

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
54
55
56
57
58
59
60

import java.util.*;

class Main {
	public static void main (String[] args) {
		int[] nums={6,2,5,8};
		int[] res=new int[nums.length];
		int[] count=new int[nums.length];
		int[] indexes=new int[nums.length];
		for(int i=0;i<nums.length;i++){
		    indexes[i]=i;
		}
		mergesort(nums,indexes,count,0,nums.length-1);
		for(int i=0;i<count.length;i++){
		    res[i]=count[i];
		}
		System.out.print(Arrays.toString(res));
	}

	static void mergesort(int[] nums,int[] indexes,int[] count,int start,int end){
	    if(start>=end) return;
	    int mid=start+(end-start)/2;
	    mergesort(nums,indexes,count,start,mid);
	    mergesort(nums,indexes,count,mid+1,end);
	    merge(nums,indexes,count,start,mid,end);
	}

	static void merge(int[] nums,int[] indexes,int[] count,int start,int mid,int end){
	    int left_ind=start;
	    int right_ind=mid+1;
	    int[]tempInd=new int[end-start+1];
	    int ind=0;
	    int cnt=0;
	    while(left_ind<=mid && right_ind<=end){
	        if(nums[indexes[left_ind]]>nums[indexes[right_ind]]){
	            tempInd[ind]=indexes[right_ind];
	            cnt++;
	            right_ind++;
	        }
	        else{
	            tempInd[ind]=indexes[left_ind];
	            count[indexes[left_ind]]+=cnt;
	            left_ind++;
	        }
	        ind++;
	    }
	    while(left_ind<=mid){
	        tempInd[ind++]=indexes[left_ind];
	        count[indexes[left_ind]]+=cnt;
	        left_ind++;
	    }
	    while(right_ind<=end){
	        tempInd[ind++]=indexes[right_ind++];
	    }
	    int k=start;
	    for(int i:tempInd){
	        indexes[k++]=i;
	    }
	}
}