题目链接：775. Global and Local Inversions

概述

题目给定一个长度为N的数组A，为[0, 1, ..., N - 1]的一种排列。全局倒置指的是 i,j 满足 0 <= i < j < N 并且 A[i] > A[j] ，局部倒置指的是i满足 0 <= i < N 并且 A[i] > A[i+1] 。问该数组的全局倒置是否等于局部倒置。

思路

这个问题暴力求解也很好办，按照题目要求扫描下数组即可。

/**
 * @param {number[]} A
 * @return {boolean}
 */
var isIdealPermutation = function(A) {
    var local = 0,
        global = 0;
    
    for(let i = 0; i < A.length - 1; i++){
        if(A[i] > A[i + 1]){
            local++;
        }
    }
    for(let i = 0; i < A.length; i++){
        for(let j = i + 1; j < A.length; j++){
            if(A[i] > A[j]){
                global++;
            }
        }
    }
    return global === local;
};

这段代码的时间复杂度为 O(n²)，只能beat 30%，有点慢。考虑下优化。

题目的两个条件可以总结为：

当0 <= i < i + k < N 并且 A[i] > A[i + k]时，则存在倒置。若k = 1，则为local，若k ≥ 1，则为global。

也就是说，如果存在k > 1，使得A[i] > A[i + k]成立，则 global !== local。

最原始的数组，为[0, 1, 2, ..., i-1, i, i+1, ..., N-1]，即A[i] = i。
假设存在k > 1，使得A[i] > A[i + k]成立，
则 A[i] != i 且 A[i] > i + 1 或 A[i] < i - 1，即|A[i]-i| > 1。

因此，只要遍历一遍数组即可得到答案。

实现

/**
 * @param {number[]} A
 * @return {boolean}
 */
var isIdealPermutation = function(A) {
    for(let i = 0; i < A.length; i++){
        if(Math.abs(A[i] - i) > 1){
            return false;
        }
    }
    return true;
};

题解合集

种星星

LeetCode题解|775. Global and Local Inversions

概述

思路

实现