Leetcode刷题剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

感谢余先声的二分解法，传送门java 二分+list.add暴力过。

class Solution {
        public int reversePairs(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
//            return reversePairsI(nums);
//            return reversePairsII(nums);
            return mergeSort(nums, 0, nums.length - 1);
        }

        //方法一：暴力法，超过时间限制
        //时间复杂度O(N^2)，空间复杂度O(1)
        private int reversePairsI(int[] nums) {
            int 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 count;
        }

        //方法二：二分法+List
        //遍历每个数，判断前面比当前数大的数的个数
        //遍历 i 的时候，如果[0,i-1]的数有序，则可以使用二分法获得前面比当前元素大的元素个数
        //假设使用二分法求得第一个比当前元素大的索引位置为firstBiggerIndex，那么前面比当前元素大的个数即为list.size()-firstBiggerIndex

        //那么如何使[0,i-1]的数有序呢，可以使用list.add(index,nums)方法将元素插入到指定的位置
        //时间复杂度O(N^2logN)，空间复杂度O(N)
        private int reversePairsII(int[] nums) {
            int len = nums.length;
            List<Integer> list = new ArrayList<>();
            list.add(nums[0]);
            int result = 0;
            for (int i = 1; i < len; i++) {
                //使用二分法获取第一个比当前元素大的索引位置，也就是二分查找的搜索左侧边界
                int firstBiggerIndex = findFirstBiggerIndex(list, nums[i]);
                result += list.size() - firstBiggerIndex;
                //假设firstBiggerIndex=1，将当前元素插入到firstBiggerIndex后，剩下的比nums[i]大的数将向后移动一位，保持了list的有序
                list.add(firstBiggerIndex, nums[i]);
            }
            return result;
        }

        private int findFirstBiggerIndex(List<Integer> list, int target) {
            int left = 0, right = list.size();
            while (left < right) {
                int mid = (left + right) >> 1;
                if (list.get(mid) > target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }

        //方法三：归并排序
        //将数组不断拆分，在合并的过程中利用数组的有序性，可以计算出一个数之后的逆序对个数
        //分别统计左右两边的逆序对数目，以及跨左半部分和右半部分的逆序对数目，然后相加即可
        //时间复杂度O(NlogN)，空间复杂度O(N)
        private int mergeSort(int[] nums, int start, int end) {
            //终止条件
            if (start >= end) return 0;
            int mid = start + (end - start) / 2;

            //左右递归并统计逆序对
            int count = mergeSort(nums, start, mid) + mergeSort(nums, mid + 1, end);

            //临时数组用于保存排序后的合并
            int[] temp = new int[end - start + 1];

            int i = start, j = mid + 1, k = 0;

            while (i <= mid && j <= end) {
                //如果左边大于右边则构成逆序对
                //左数组i位置及其后的数值均比右数值j位置大，因此加上i位置及其后数值的长度
                //假如左边是[7,8]，右边是[5,6]，然后i指向7
                //j指向5，那么5和7、8都构成了逆序对，也就是此时有两对新的逆序对
                //所以可以得出：count += mid - i + 1
                count += nums[i] > nums[j] ? mid - i + 1 : 0;
                temp[k++] = nums[i] > nums[j] ? nums[j++] : nums[i++];
            }

            while (i <= mid) {
                temp[k++] = nums[i++];
            }
            while (j <= end) {
                temp[k++] = nums[j++];
            }

            System.arraycopy(temp, 0, nums, start, temp.length);
            return count;
        }
    }

 

本文地址：https://blog.csdn.net/Bonbon_wen/article/details/112253941