LeetCode 775. 全局倒置与局部倒置

775. 全局倒置与局部倒置

 

【归并排序】显然全局倒置就是求整体的逆序对，用归并排序的思想可以在O(nlogn)的复杂度下求出逆序对的个数。

class Solution {
 
    // 9:56 15
 
    int[] nums, tmp;
    int n;
 
    int global(int l, int r) {
        if (l == r) return 0;
        int m = (l + r) >> 1;
        int ret = 0;
        ret += global(l, m); ret += global(m + 1, r);
        int i = l, j = m + 1, k = 0;
        while (i <= m && j <= r) {
            if (nums[i] > nums[j]) {
                tmp[k++] = nums[i++];
                ret += r - j + 1;
            } else {
                tmp[k++] = nums[j++];
            }
        }
        while (i <= m) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];
        for (i = l, k = 0; i <= r;) nums[i++] = tmp[k++];
        return ret;
    }
 
    int local() {
        int ret = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) ret++;
        }
        return ret;
    }
 
    public boolean isIdealPermutation(int[] nums) {
        this.nums = nums;
        n = nums.length;
        tmp = new int[n];
        if (local() == global(0, n - 1)) return true;
        return false;
    }
}

【数学】我们发现局部倒置一定是全局倒置，如果数量相同就是所有的全局倒置都是局部的，也就是都是相邻的，那么只需要检查一下有没有不相邻的倒置即可。

 

class Solution {
 
    // 维护后缀最小值
    // 10:56 3
 
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length, min = nums[n - 1];
        for (int i = n - 3; i >= 0; i--) {
            if (nums[i] > min) return false;
            min = Math.min(nums[i + 1], min);
        }
        return true;
    }
}