FilesExpand file tree

 master

/

inversepairs.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

41 lines (41 loc) · 1.23 KB

 master

/

inversepairs.java

Top

File metadata and controls

• Code
• Blame

41 lines (41 loc) · 1.23 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

public class Solution {

public int InversePairs(int [] array) {

if(array==null||array.length==0)

return 0;

int [] copy = new int[array.length];

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

copy[i]=array[i];

}

return mergesort(array,copy,0,array.length-1);

}

int mergesort(int [] array,int[] copy,int start,int end){

if(start==end){

copy[start]=array[start];

return 0;

}

int mid=(start+end)/2;

int left =mergesort(copy,array,start,mid);

int right = mergesort(copy,array,mid+1,end);

int i=mid,j=end,count=0,index=end;

while(i>=start&&j>mid){

if(array[i]>array[j]){

count+=j-mid;

copy[index--]=array[i--];

if(count>=1000000007)//数值过大求余

{

count%=1000000007;

}

}

else{

copy[index--]=array[j--];

}

}

while(i>=start){

            copy[index--]=array[i--];

        }

        while(j>mid){

            copy[index--]=array[j--];

        }

        return (count+left+right)%1000000007;

}

}