数组中的逆序对

// 暴力解法
    public int InversePairs1 (int[] nums) {
        long count = 0;
        for(int i=0;i<nums.length-1;i++){
            for(int j = i+1;j<nums.length;j++){
                if(nums[i] > nums[j]){
                    count++;
                }
            }
        }
        return (int)(count % 1000000007);
    }
    // 插入排序
    public int InversePairs2 (int[] nums) {
        long count = 0;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(nums[nums.length-1]);
        for(int i=nums.length-2;i >= 0;i--){
            count += InversePairs_insert(list,nums[i]);
        }
        return (int)(count % 1000000007);
    }

    public int InversePairs_insert (ArrayList<Integer> list,int data) {
        int s=0,e=list.size()-1;
        int mid = 0;
        while(s<=e){
            mid = (s+e)/2;
            if(list.get(mid) == data){
                break;
            }else if(list.get(mid) > data){
                e = mid - 1;
            }else{
                s = mid + 1;
            }
        }
        if(s > mid){
            list.add(mid+1,data);
            return mid + 1;
        }else{
            list.add(mid,data);
            return mid;
        }
    }
    // 归并
    public int InversePairs (int[] nums) {
        if(nums.length < 2) return 0;
        int[] temp = new int[nums.length];
        int count = InversePairs_sort(nums,0,nums.length-1,temp);
        return count;
    }

    public int InversePairs_sort(int[] nums,int s,int e,int[] temp) {
        if(s >= e) return 0;
        int mid = (s+e)/2;
        int res = InversePairs_sort(nums,s,mid,temp) 
                + InversePairs_sort(nums,mid+1,e,temp);
        res = res % 1000000007;
        int i = s,j = mid+1;
        for(int k=s;k<=e;k++){
            temp[k] = nums[k];
        }
        for(int k=s;k<=e;k++){
            if(i == mid+1){
                nums[k] = temp[j++];
            }else if(j == e+1 || temp[i] <= temp[j]){
                nums[k] = temp[i++];
            }else{
                nums[k] = temp[j++];
                res += mid - i + 1;
            }
        }
        return res % 1000000007;
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        // write code here
        // 左程云老师讲过，通过归并排序过程中的左右两个字串的比较，可以实现逆序对的统计

        // 算法的时间复杂度O(NlogN)，空间复杂度O(N)

        // 调用归并排序的递归执行方法
        int count = process(nums, 0, (nums.length - 1));
        // 注意题目要求，对1000000007取模
        return count % 1000000007;
    }

    // 递归执行方法
    public int process(int[] nums, int l, int r) {
        // 递归出口
        if (l == r) {
            return 0;
        }
        // 计算中间索引
        int mid = (l + r) / 2;
        // 返回递归过程产生的逆序对数量
        int count = process(nums, l, mid) +
                    process(nums, mid + 1, r) +
                    compareAndMerge(nums, l, mid, r);
        // 注意题目要求，对1000000007取模
        return count % 1000000007;
    }

    // 比较与归并方法
    public int compareAndMerge(int[] nums, int l, int mid, int r) {
        // 记录逆序对的个数
        int count = 0;

        // 比较，归并
        int[] tempNums = new int[r - l + 1];
        // nums的左半区下标
        int leftIndex = l;
        // nums的右半区下标
        int rightIndex = mid + 1;
        // tempNums的下标
        int tempIndex = 0;
        while (leftIndex <= mid && rightIndex <= r) {
            // 请注意，归并排序merge的一个前提是，左右两个半区各自有序
            if (nums[leftIndex] < nums[rightIndex]) {
                // 左边 < 右边，则左边先进入tempNums中，leftIndex和tempIndex都++
                tempNums[tempIndex] = nums[leftIndex];
                leftIndex++;
            } else {
                // 左边 > 右边，则右边先进入tempNums中，rightIndex和tempIndex都++
                // 注意！此时算作逆序对！
                tempNums[tempIndex] = nums[rightIndex];
                rightIndex++;
                // tempNums[leftIndex]大，说明从leftIndex到mid上的数都更大，逆序数要全算上
                count += (mid - leftIndex + 1);
                // 注意题目要求，对1000000007取模
                count %= 1000000007;
            }
            tempIndex++;
        }
        // 此时退出了循环，要么leftIndex越界，要么rightIndex越界，以下两个while最多执行一个
        while (leftIndex <= mid) {
            // 右边的rightIndex先越界了，说明左边剩下的元素都比右边的大，把左边剩下的元素全部送进tempNums中
            // 注意！这里的逆序对已经被上一个while中考虑到了
            tempNums[tempIndex] = nums[leftIndex];
            leftIndex++;
            tempIndex++;
        }
        while (rightIndex <= r) {
            // 左边的leftIndex先越界了，说明右边剩下的元素都比左边的大，把右边剩下的元素全部送进tempNums中
            tempNums[tempIndex] = nums[rightIndex];
            rightIndex++;
            tempIndex++;
        }

        // 最后，把tempNums排好序的内容写回nums的对应位置
        for (int i = 0; i < tempNums.length; i++) {
            nums[l + i] = tempNums[i];
        }

        // 返回统计到的逆序数
        return count;
    }
}

归并排序

public class Solution {
    public static final int MOD = 1000000007;

    public int InversePairs (int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] nums, int l, int r) {
        if (l == r) {
            return 0;
        } 
        int mid = (l + r) >> 1;
        int lres = mergeSort(nums, l, mid);
        int rres = mergeSort(nums, mid + 1, r);

        int left = l, right = mid + 1, ans = (lres + rres) % MOD;
        int[] tmp = new int[r - l + 1];
        int idx = 0;
        while (left <= mid && right <= r) {
            if (nums[left] <= nums[right]) {
                tmp[idx++] = nums[left++];
            } else {
                tmp[idx++] = nums[right++];
                ans = (ans + mid - left + 1) % MOD;
            }
        } 
        while (left <= mid) tmp[idx++] = nums[left++];
        while (right <= r) tmp[idx++] = nums[right++];
        for (int i = 0; i < idx; i++) {
            nums[l + i] = tmp[i];
        }

        return ans;
    }
}

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);
    }
}

public class Solution {
    public int InversePairs(int [] array) {
        if(array.length == 0) return 0;
        long P =0L;
        for(int i =0; i < array.length - 1; i++)
            for(int j = i + 1; j < array.length; j++){
                if(array[i] > array[j]) P++;
            }
        return (int)(P % 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];
        }
        
    }
}

public class Solution {
    public int InversePairs(int [] array) {
        if (array == null || array.length <= 0 ) {
            return 0;
        }
        int[] temp = new int[array.length];
        return sort(array, 0, array.length-1, temp) % 1000000007;

    }
    private int sort(int[] array, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }
        int mid = (right - left) / 2 + left;
        int leftPairCount = sort(array, left, mid, temp);
        int rightPairCount = sort(array, mid + 1, right, temp);
        int tmpPairCount = merge(array, left, mid, right, temp);
        return leftPairCount + rightPairCount + tmpPairCount;

    }

    private int merge(int[] array, int left, int mid, int right, int[] temp) {
        int start1 = left;
        int start2 = mid + 1;
        int index = 0;
        int computeReversePairs = 0;
        while (start1 <= mid && start2 <= right) {

            if (array[start1] <= array[start2]) {
                temp[left + index] = array[start1];
                start1++;

            } else {
                temp[left + index] = array[start2];
                start2++;
                computeReversePairs = (computeReversePairs+(mid-start1+1))%1000000007;
            }
            index++;
        }

        while (start1 <= mid) {
            temp[left + index] = array[start1];
            start1++;
            index++;
        }
        while (start2 <= right) {
            temp[left + index] = array[start2];
            start2++;
            index++;
        }
        //将temp覆盖原来的数组中的顺序
        while (left <= right) {
            array[left] = temp[left];
            left++;
        }
        return computeReversePairs;
    }
}