文章目录
  1. 1. 题意描述
  2. 2. 题意翻译:
  3. 3. 思路:
  4. 4. 代码参考:

题意描述

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:

1、A will be a permutation of [0, 1, …, A.length - 1].

2、A will have length in range [1, 5000].

3、The time limit for this problem has been reduced.

题意翻译:

给一个 0-N 全排列后的数组的乱序,定义两种逆序对,第一种叫做全局逆序对,另外一种叫做局部逆序对,分别给出了这两种逆序对的定义。然后判断给定数组里两种逆序对的个数是否相同。

思路:

可以从题意里看出,全局逆序对的个数是大于等于局部逆序对的,相等的情况是全部是局部逆序对,这时是不会出现 A[i] > A[i+2] 的。以此为判断条件,可想出 O(n) 的算法解决,

代码参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean isIdealPermutation(int[] A) {
/*
* 基本思路:
* 1、求 global inversion
* 2、求 local inversion (其中 global >= local)
* 3、判断 global inversion == local inversion
*/

int len = A.length;

int max = 0;

for(int i=0 ; i<len-2 ; i++){
max = Math.max(max , A[i]);
if (max > A[i+2]) return false;
}
return true;
}
}
文章目录
  1. 1. 题意描述
  2. 2. 题意翻译:
  3. 3. 思路:
  4. 4. 代码参考: