[剑指offer][Java]数组中的逆序对

傷城~ 2022-05-12 03:14 146阅读 0赞

# 题目 #

链接：[https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5][https_www.nowcoder.com_questionTerminal_96bd6684e04a44eb80e6a68efc0ec6c5]  
来源：牛客网

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

# 代码 #

注意点：

*  归并排序：Java不能切片，所以用start,end，mid控制数组内切片长度
 *  Java

public class Solution {
        private int count;
        public int InversePairs(int [] array) {
            count = 0;
            if(array != null){
                mergeSort(array, 0, array.length - 1);
            }
            return count;
        }
    
        private void mergeSort(int[] a, int start, int end){
            if(start >= end)
                return;
            int mid = start + (end - start) / 2;
            mergeSort(a, start, mid);
            mergeSort(a, mid+1, end);
            merge(a,start,mid,end);
        }
    
        private void merge(int[] a, int start, int mid, int end){
            int[] temp = new int[end-start+1];
            int i = start, j = mid + 1, k = 0;
            while (i <= mid && j <= end) {
                if (a[i] <= a[j])
                    temp[k++] = a[i++];
                else {
                    temp[k++] = a[j++];
                    // ai大于aj，由于归并，所以相反的必定是和所有前面的数字，所以是mid到最左边i中间的数的个数
                    count = (count + mid - i + 1) % 1000000007;
                }
            }
    
            while (i <= mid)
                temp[k++] = a[i++];
            while (j <= end)
                temp[k++] = a[j++];
            for(k=0;k<temp.length;k++){ //将临时数组的数字写回a数组！
                a[start+k] = temp[k];
            }
        }
    }

[https_www.nowcoder.com_questionTerminal_96bd6684e04a44eb80e6a68efc0ec6c5]: https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5