题目

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:

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

Example 2:

  1. Input: A = [1,2,0]
  2. Output: false
  3. 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.

题意

给定一个数组，如果 i < j 且 A[i] > A[j]，则称存在一个全局倒置；如果 A[i] > A[i+1]，则称存在一个局部倒置。判断全局倒置的数量是否和局部倒置相同。

思路

最直接的方法是计算局部倒置和全局倒置(归并排序中判断)，并进行比较。

用到题目给的条件：A是 0 ~ N-1 的一个排列，如果不存在倒置，A = [0, 1, 2, 3, …, N-1]，如果存在倒置，相当于在这个递增数组中选两个元素互换。局部倒置一定是全局倒置，如果两者数量相等，则所有全局倒置也一定是局部倒置，相当于在这个递增数组中仅选取相邻的元素进行互换，因此只要遍历一遍数组，判断 A[i] 的值是否在 (i - 1, i, i + 1)中即可。

代码实现

Java

直接计算

  1. class Solution {
  2.     public boolean isIdealPermutation(int[] A) {
  3.         return calcLocal(A) == calcGlobal(A);
  4.     }
  6.     private int calcLocal(int[] A) {
  7.         int local = 0;
  8.         for (int i = 0; i < A.length - 1; i++) {
  9.             if (A[i] > A[i + 1]) {
  10.                 local++;
  11.             }
  12.         }
  13.         return local;
  14.     }
  16.     private int calcGlobal(int[] A) {
  17.         int global = 0;
  18.         for (int step = 1; step < A.length; step *= 2) {
  19.             for (int start = 0; start + step < A.length; start += 2 * step) {
  20.                 int left = start, leftEnd = left + step - 1;
  21.                 int right = start + step, rightEnd = Math.min(A.length - 1, right + step - 1);
  22.                 int[] tmp = new int[rightEnd - left + 1];
  23.                 int index = 0;
  24.                 while (left <= leftEnd || right <= rightEnd) {
  25.                     if (left > leftEnd || right > rightEnd) {
  26.                         tmp[index++] = left > leftEnd ? A[right++] : A[left++];
  27.                     } else if (A[left] <= A[right]){
  28.                         tmp[index++] = A[left++];
  29.                     } else {
  30.                         global += leftEnd - left + 1;
  31.                         tmp[index++] = A[right++];
  32.                     }
  33.                 }
  34.                 for (int i = start; i <= rightEnd; i++) {
  35.                     A[i] = tmp[i - start];
  36.                 }
  37.             }
  38.         }
  39.         return global;
  40.     }
  41. }

遍历判断

  1. class Solution {
  2.     public boolean isIdealPermutation(int[] A) {
  3.         for (int i = 0; i < A.length; i++) {
  4.             if (Math.abs(A[i] - i) > 1) return false;
  5.         }
  6.         return true;
  7.     }
  8. }