Сложность: medium
Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].
Число глобальных инверсий — это количество различных пар (i, j), где:
0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:
0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.
Пример:
Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.
👨💻 Алгоритм:
1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1.
2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии.
3⃣Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false.
😎 Решение:
class Solution {
func isIdealPermutation(_ A: [Int]) -> Bool {
let N = A.count
for i in 0..<N {
for j in i+2..<N {
if A[i] > A[j] {
return false
}
}
}
return true
}
}Ставь 👍 и забирай 📚 Базу знаний