数组中的逆序对

发表于 | 分类于 ，

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

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
public class Solution {

    public int InversePairs(int [] array) {
         if(array == null || array.length == 0 || array.length == 1) 
             return 0;
        return sort(array, 0, array.length - 1);
    }
    public int sort(int[] arr, int low, int high){
        if(low < high){
            int mid = (low + high) / 2;
            return sort(arr, low, mid) 
                + sort(arr, mid + 1, high) 
                + merge(arr, low, high);   
        }
        return 0;
         
    }
    public int merge(int[] arr, int low, int high){
        int i = low;
        int mid = (low + high) / 2;
        int j = mid + 1;
        int result = 0;
        int[] tmp = new int[high - low + 1];
        int k = 0;
        while(i <= mid && j <= high){
            if(arr[i] > arr[j]){
                result++;
                tmp[k++] = arr[j++];
            }else{
                tmp[k++] = arr[i++];
            }
        }
        if(i <= mid){
            result += (mid - i) * (high - mid);
            while(i <= mid){
                tmp[k++] = arr[i++];
            }
        }else{
            while(j <= high){
                tmp[k++] = arr[j++];
            }
        }
        for(int p = 0; p <= tmp.length - 1; p++){
            arr[low + p] = tmp[p];
        }
        return result;
    }
}