数组中的逆序对

归并排序

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

public class Solution {
    int ans = 0;
    public int InversePairs(int [] nums) {
        if(nums.length < 1) return 0;
        mergeSort(nums, 0, nums.length - 1);
        return ans;
    }
    
    void mergeSort(int[] nums, int left, int right){
        if(left >= right) return;
        
        int mid = left + (right - left) / 2;
        
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid , right);
    }
    
    void merge(int[] nums, int left, int mid, int right) {
        int[] copy = new int[right - left + 1];
        
        int l1 = left, l2 = mid + 1, idx = 0;
        while(l1 <= mid && l2 <= right) {
            if(nums[l1] < nums[l2]) {
                copy[idx++] = nums[l1++];
            }else{
                copy[idx++] = nums[l2++];
                ans += mid - l1 + 1;
                ans %= 1000000007;
            }
        }
        while(l1 <= mid) copy[idx++] = nums[l1++];
        while(l2 <= right) copy[idx++] = nums[l2++];
        
        for(int i = 0; i < copy.length; ++i) {
            nums[left + i] = copy[i];
        }
    }
}