Сложность: 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 {
public:
bool isIdealPermutation(vector<int>& A) {
int N = A.size();
for (int i = 0; i < N; ++i)
for (int j = i + 2; j < N; ++j)
if (A[i] > A[j]) return false;
return true;
}
};Ставь 👍 и забирай 📚 Базу знаний