數(shù)組 A 是 [0, 1, ..., N - 1] 的一種排列粘勒，N 是數(shù)組 A 的長(zhǎng)度。全局倒置指的是 i,j 滿足 0 <= i < j < N 并且 A[i] > A[j] 屎即，局部倒置指的是 i 滿足 0 <= i < N 并且 A[i] > A[i+1] 庙睡。
當(dāng)數(shù)組 A 中全局倒置的數(shù)量等于局部倒置的數(shù)量時(shí)事富，返回 true 。
示例 :
輸入: A = [1,0,2]
輸出: true
解釋: 有 1 個(gè)全局倒置乘陪，和 1 個(gè)局部倒置统台。
示例 2:
輸出: false
解釋: 有 2 個(gè)全局倒置，和 1 個(gè)局部倒置啡邑。
注意:
- A 是 [0, 1, ..., A.length - 1] 的一種排列
- A 的長(zhǎng)度在 [1, 5000]之間
這個(gè)問(wèn)題的時(shí)間限制已經(jīng)減少了贱勃。
思路:
- 局部倒置屬于全局倒置
- 存在非局部倒置的全局倒置時(shí)返回false(即間隔一位元素大于)
- A是從0開(kāi)始不間斷序列的一種排序
- 時(shí)間限制極短
- 記錄一種簡(jiǎn)潔高效的寫(xiě)法,傳送門(mén)
代碼:
public boolean isIdealPermutation(int[] A) {
for (int i = 0; i < A.length; i++) {
if (A[i] - i > 1 || A[i] - i < -1)
return false;
}
return true;
}
總結(jié):
- 由于序列不間斷,當(dāng)存在一個(gè)數(shù)偏離升序排序時(shí)兩單位的位置時(shí),必然存在非局部倒置的全局倒置
- 代碼復(fù)制,小腦瓜子能看出點(diǎn)端倪,寫(xiě)出來(lái)就難咯
