Problem
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:
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.
Solution1: Brute Force (TLE)
Time complexity: O(n^2)
Space complexity: O(1)
C++
|
|
// Author: Huahua // Running time: TLE (208/208 test cases passed) class Solution { public: bool isIdealPermutation(vector<int>& A) { const int n = A.size(); int local = 0; for (int i = 0; i < n - 1; ++i) if (A[i] > A[i + 1]) ++local; int global = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (A[i] > A[j] && ++global > local) return false; return global == local; } }; |
Solution2: MergeSort
Time complexity: O(nlogn)
Space complexity: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// Author: Huahua // Running time: 52 ms (<96.42%) class Solution { public: bool isIdealPermutation(vector<int>& A) { const int n = A.size(); int local = 0; for (int i = 0; i < n - 1; ++i) if (A[i] > A[i + 1]) ++local; tmp = vector<int>(n); int global = mergeSort(A, 0, n - 1); return global == local; } private: vector<int> tmp; int mergeSort(vector<int>& A, int l, int r) { if (l >= r) return 0; const int len = r - l + 1; int m = (r - l) / 2 + l; int inv = mergeSort(A, l, m) + mergeSort(A, m + 1, r); int i = l; int j = m + 1; int k = 0; while (i <= m && j <= r) { if (A[i] <= A[j]) { tmp[k++] = A[i++]; } else { tmp[k++] = A[j++]; inv += m - i + 1; } } while (i <= m) tmp[k++] = A[i++]; while (j <= r) tmp[k++] = A[j++]; std::copy(tmp.begin(), tmp.begin() + len, A.begin() + l); return inv; } }; |
C#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Author: Huahua // Running time: 208 ms public class Solution { public bool IsIdealPermutation(int[] A) { var n = A.Length; var localInv = 0; for (var i = 1; i < n; ++i) if (A[i] < A[i - 1]) ++localInv; tmp = new int[n]; var globalInv = MergeSort(A, 0, n - 1); return localInv == globalInv; } private int[] tmp; private int MergeSort(int[] A, int l, int r) { if (l >= r) return 0; int m = (r - l) / 2 + l; int inv = MergeSort(A, l, m) + MergeSort(A, m + 1, r); int i = l; int j = m + 1; int k = 0; while (i <= m && j <= r) { if (A[i] <= A[j]) { tmp[k++] = A[i++]; } else { inv += m - i + 1; tmp[k++] = A[j++]; } } while (i <= m) tmp[k++] = A[i++]; while (j <= r) tmp[k++] = A[j++]; Array.Copy(tmp, 0, A, l, k); return inv; } } |
Solution3: Input Property
Input is a permutation of [0, 1, …, N – 1]
Time Complexity: O(n)
Space Complexity: O(1)
|
|
// Author: Huahua // Running time: 40 ms (<99.26%) 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; } }; |