数组中的逆序对

2021-01-05

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

难度困难405

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

示例 1:

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

限制：

1	0 <= 数组长度 <= 50000

1
2
3

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

归并排序

class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        temp = new int[n];
        return mergeSort(nums,0,n-1);
    }

    int [] temp ;
    public int mergeSort(int []nums,int l,int r){
        if(l>=r)return 0;
        int m = l+(r-l)/2;
        int res= mergeSort(nums,l,m) + mergeSort(nums,m+1,r);

        int cnt = 0,i=l,j=m+1;
        while(i<=m&&j<=r){
            // 如果左边的元素小于右边的元素,说明没有逆序
            // 如果左边的元素大于右边的元素,说明左边的元素是逆序的
            // 逆序的数量是从i到m之间的所有元素
            if(nums[i]<=nums[j]){
                temp[cnt++] = nums[i++];
            }else{
                temp[cnt++] = nums[j++];
                // 一开始这里我不明白
                // 从i到m之间的所有元素都是逆序的,统计从i到m之间的数字的数量
                res += m - i + 1;
            }
        }
        // 左边的没用完
        while(i<=m)temp[cnt++] = nums[i++];
        // 右边的没用完
        while(j<=r)temp[cnt++] = nums[j++];
        // 放回原来的数组当中
        for(int k=0;k<r-l+1;k++){
            nums[l+k] = temp[k];
        }
        return res;
    }
}

树状数组

class Solution {
    public int reversePairs(int[] nums) {
        if(nums==null||nums.length==0)return 0;
        int len = nums.length;
        //先对数组进行离散化，解决过大的数字
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = nums[i];
        }
        Arrays.sort(nums);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i + 1);
        }
        FenwickTree fenwickTree = new FenwickTree(len);

        int res = 0;
        for (int i = 0; i < len; i++) {
            int index = map.get(arr[i]);
            fenwickTree.update(index, 1);
            res += (i + 1 - fenwickTree.query(index));
        }
        return res;
    }
      private class FenwickTree {

        int len = 0;
        int[] tree;

        public FenwickTree(int n) {
            this.len = n;
            tree = new int[n + 1];
        }


        public void update(int i, int num) {
            while (i <= len) {
                tree[i] += num;
                i += lowbit(i);
            }
        }

        public int query(int i) {
            int sum = 0;
            while (i > 0) {
                sum += tree[i];
                i -= lowbit(i);
            }
            return sum;
        }


        public int lowbit(int x) {

            return x & (-x);
        }

    }
}

官方题解：树状数组

class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        int[] tmp = new int[n];
        System.arraycopy(nums, 0, tmp, 0, n);
        // 离散化
        Arrays.sort(tmp);
        for (int i = 0; i < n; ++i) {
            nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;
        }
        // 树状数组统计逆序对
        BIT bit = new BIT(n);
        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            ans += bit.query(nums[i] - 1);
            bit.update(nums[i]);
        }
        return ans;
    }
}

class BIT {
    private int[] tree;
    private int n;

    public BIT(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }

    public static int lowbit(int x) {
        return x & (-x);
    }

    public int query(int x) {
        int ret = 0;
        while (x != 0) {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    public void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowbit(x);
        }
    }
}

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

归并排序

public class Solution {
    public int reversePairs(int[] nums) {
        int len = nums.length;

        if (len < 2) {
            return 0;
        }

        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }

        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    /**
     * nums[left..right] 计算逆序对个数并且排序
     *
     * @param nums
     * @param left
     * @param right
     * @param temp
     * @return
     */
    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        if (nums[mid] <= nums[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int crossPairs = mergeAndCount(nums, left, mid, right, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    /**
     * nums[left..mid] 有序，nums[mid + 1..right] 有序
     *
     * @param nums
     * @param left
     * @param mid
     * @param right
     * @param temp
     * @return
     */
    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {

            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
                count += (mid - i + 1);
            }
        }
        return count;
    }
}

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