【剑指offer】面试题51：数组中的逆序对

桃扇骨 2022-06-11 05:58 162阅读 0赞

## 题目 ##

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

## 思路 ##

有空再补上 0.0  
使用归并排序

## 代码 ##

/**
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
     * 输入一个数组,求出这个数组中的逆序对的总数P。
     * 并将P对1000000007取模的结果输出。 即输出P%1000000007
     * 
     * @author peige
     */
    public class _51_InversePairs {
        
    
        private static int N = 1000000007;
    
        private int inversePairs;
    
        public int InversePairs(int [] array) {
            if(array == null || array.length <= 1)
                return 0;
            inversePairs = 0;
            mergeSort(array);
            return inversePairs;
        }
    
        private void mergeSort(int[] array) {
            int[] tmp = new int[array.length];
            mergeSort(array, 0, array.length - 1, tmp);
        }
    
        private void mergeSort(int[] array, int low, int high, int[] tmp) {
            if(low >= high)
                return;
            int mid = low + (high - low) / 2;
            mergeSort(array, low, mid, tmp);
            mergeSort(array, mid + 1, high, tmp);
            merge(array, low, mid, high, tmp);
        }
    
        private void merge(int[] array, int low, int mid, int high, int[] tmp) {
            int i = mid;
            int j = high;
            int pairs = high - mid;
            for(int k = low; k <= high; ++k)
                tmp[k] = array[k];
            for(int k = high; k >= low; --k) {
                if(i < low) {
                    array[k] = tmp[j--];
                }
                else if(j < mid + 1) {
                    array[k] = tmp[i--];
                }
                else if(tmp[i] > tmp[j]) {
                    array[k] = tmp[i--];
                    inversePairs = (inversePairs + pairs) % N;
                }
                else {
                    array[k] = tmp[j--];
                    --pairs;
                }
            }
        }
    }

## 测试 ##

public class _51_Test {
        
    
        public static void main(String[] args) {
            test1();
            test2();
            test3();
        }
    
        /**
         * 5,6,3,2
         */
        private static void test1() {
            _51_InversePairs ip = new _51_InversePairs();
            int n = ip.InversePairs(new int[] {
       5,6,3,2});
            MyTest.equal(n, 5);
    
            n = ip.InversePairs(new int[] {
       4,2,3,4});
            MyTest.equal(n, 2);
    
            n = ip.InversePairs(new int[] {
       6,6,4,2,1,7});
            MyTest.equal(n, 9);
        }
    
        /**
         * 边界
         */
        private static void test2() {
            _51_InversePairs ip = new _51_InversePairs();
            int n = ip.InversePairs(new int[] {
       1,2,3,4});
            MyTest.equal(n, 0);
    
            n = ip.InversePairs(new int[] {
       4,3,2,1});
            MyTest.equal(n, 6);
    
            n = ip.InversePairs(new int[] {
       1});
            MyTest.equal(n, 0);
        }
    
        /**
         * 极端
         */
        private static void test3() {
            _51_InversePairs ip = new _51_InversePairs();
            int n = ip.InversePairs(new int[0]);
            MyTest.equal(n, 0);
    
            n = ip.InversePairs(null);
            MyTest.equal(n, 0);
        }
    
    }