面试必刷TOP101：20、数组中的逆序对

题目

题解

解法一：暴力法

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        long total=0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j <nums.length; j++) {
                if (nums[i]>nums[j]){
                    total++;
                }
            }
        }
        return (int) (total%1000000007);
    }
}

解法二：归并排序

//归并排序Java版
public class Solution {
    int count=0;
    public int InversePairs(int [] array) {
        mergeSort(array,0,array.length-1);
        return count;
    }

    public void mergeSort(int [] array, int left, int right){
        if(left >= right) return;
        int mid = (left+right)/2;
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }

    public void merge(int [] array, int left, int mid, int right){
        int[] temp=new int[right-left+1];
        int i=left, j=mid+1;
        int t=0;

        while(i<=mid && j<=right){
            if(array[i]<=array[j]){
                temp[t++]=array[i++];
            }else{
                count=count+(mid-i+1);
                count%=1000000007; //在这里取模
                temp[t++]=array[j++];
            }
        }

        while(i<=mid){
            temp[t++]=array[i++];
        }
        while(j<=right){
            temp[t++]=array[j++];
        }

        for(int k=0;k<temp.length;k++){
            array[left+k]=temp[k];
        }
        
    }
}