题目描述：

LeetCode 775. Global and Local Inversions

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:

Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.

Note:

• A will be a permutation of [0, 1, ..., A.length - 1].
• A will have length in range [1, 5000].
• The time limit for this problem has been reduced.

题目大意：

给定排列A，判断其全局逆序对和局部逆序对的个数是否相等。

局部逆序对是指：0 <= i < N 并且 A[i] > A[i+1]

全局逆序对是指：i < j 并且 0 <= i < j < N 并且 A[i] > A[j]

解题思路：

全局逆序对可以用树状数组求解

局部逆序对遍历一次数组即可

Java代码：

class Solution {
    public boolean isIdealPermutation(int[] A) {
        return localInversion(A) == globalInversion(A);
    }
    public int localInversion(int[] A) {
        int sum = 0;
        for (int i = 0; i < A.length - 1; i++) {
            if (A[i] > A[i + 1]) sum++;
        }
        return sum;
    }
    public int globalInversion(int[] nums) {
        FenwickTree ft = new FenwickTree(nums.length);
        int[] idexes = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            idexes[nums[i]] = i + 1;
        }
        int ans = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            ans += ft.sum(idexes[i] - 1);
            ft.add(idexes[i], 1);
        }
        return ans;
    }
    class FenwickTree {
        int n;
        int sums[];
        public FenwickTree(int n) {
            this.n = n;
            sums = new int[n + 1];
        }
        void add(int x, int val) {
            while (x <= this.n) {
                sums[x] += val;
                x += lowbit(x);
            }
        }
        int lowbit(int x) {
            return x & -x;
        }
        int sum(int x) {
            int res = 0;
            while (x > 0) {
                res += sums[x];
                x -= lowbit(x);
            }
            return res;
        }
    }

}

 

本文链接：http://bookshadow.com/weblog/2018/01/28/leetcode-global-and-local-inversions/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码