[leetcode]Global and Local Inversions-全局、本地逆序

原题翻译

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.
我们有一个序列 A [0, 1, ..., N - 1], N 同时也是序列长度。
The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].
全局逆序判定规则:i < j & 0 <= i < j < N & A[i] > A[j]。
The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].
本地逆序判定规则:0 <= i < N & A[i] > A[i+1]。
Return true if and only if the number of global inversions is equal to the number of local inversions.
全局逆序和本地逆序数量相同返回 true。
例子 1 :

Input: A = [1,0,2]
Output: true
说明: 一个全局,一个本地.
Input: A = [1,2,0]
Output: false
说明: 连个全局,一个本地
  • A 在 [0, 1, ..., A.length - 1] 范围内.
  • A 长度限制:[1, 5000].
  • 时间限制被缩短

基本思路

本地逆序一定是全局逆序,一旦出现纯纯的全局逆序(不属于本地逆序的全局逆序),两种逆序数量一定不相同。
本题就变成寻找全局逆序了,由于本题给出的序列特殊,整个序列的元素就是索引元素的乱序。所以,当元素和其索引的差值大于一,说明该元素一定为纯全局逆序。

class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        for(int i=0;i<A.size();i++)
            if(abs(A[i] - i)> 1)  return false;
        return true;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注