775. Global and Local Inversions
775. Global and Local Inversions
LWC 69: 775. Global and Local Inversions
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.
思路： local inversion 很容易求解，遍历一遍O(n)结束，global inversion实际上就是求逆序对的个数。所以此题我们可以分别求解local inversion和global inversion之后再check。逆序对采用分治算法，详见http://blog.csdn.net/u014688145/article/details/79059221
Java版本：
public boolean isIdealPermutation(int[] A) {
int local = 0;
int n = A.length;
for (int i = 0; i < n; ++i) {
if (i + 1 < n && A[i] > A[i + 1]) local ++;
}
count = 0;
num = A;
merge(0, n);
return local == count;
}
int count = 0;
int[] num;
void merge(int s, int e) {
if (e - s <= 1) return;
int m = (s + e) / 2;
merge(s, m);
merge(m, e);
for (int i = s, j = m; i < m; ++i) {
while (j < e && num[i] > num[j]) j ++;
count += j - m;
}
mergeSort(s, e);
}
void mergeSort(int s, int e) {
int m = (s + e) / 2;
int[] aux = new int[e - s];
int i = s;
int j = m;
int k = 0;
while (i < m && j < e) {
if (num[i] < num[j]) aux[k++] = num[i++];
else aux[k++] = num[j++];
}
while (i < m) aux[k++] = num[i++];
while (j < e) aux[k++] = num[j++];
for (int t = 0, l = s; l < e; ++l) num[l] = aux[t++];
}1. 所有的local inversion 都是 global inversion。 2. 为了让local inversion == global inversion，让A中只存在local inversion即可。 3. A中只存在local inversion的充分必要条件是：对所有local inversion排序后得到A是有序的。
Python版本：
class Solution(object):
def isIdealPermutation(self, A):
"""
:type A: List[int]
:rtype: bool
"""
n = len(A)
for i in xrange(1, n):
if A[i - 1] == A[i] + 1:
A[i - 1], A[i] = A[i], A[i - 1]
elif A[i - 1] != i - 1:
return False
return True当然，你还可以这样：
The original order should be [0, 1, 2, 3, 4…], the number i should be on the position i. We just check the offset of each number, if the absolute value is larger than 1, means the number of global inversion must be bigger than local inversion, because a local inversion is a global inversion, but a global one may not be local.
Python版本：
class Solution(object):
def isIdealPermutation(self, A):
"""
:type A: List[int]
:rtype: bool
"""
return all(abs(v - i) <= 1 for v, i in enumerate(A))