775. Global and Local Inversions

public class Solution {
    public bool IsIdealPermutation(int[] A) {
        int N = A.Length;
        for (int i = 0; i < N; ++i)
            for (int j = i + 2; j < N; ++j)
                if (A[i] > A[j]) return false;
        return true;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    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;
    }
}

class Solution {
    public boolean isIdealPermutation(int[] A) {
        int N = A.length;
        for (int i = 0; i < N; ++i)
            for (int j = i + 2; j < N; ++j)
                if (A[i] > A[j]) return false;
        return true;
    }
}

class Solution {
    isIdealPermutation(A) {
        const N = A.length;
        for (let i = 0; i < N; ++i)
            for (let j = i + 2; j < N; ++j)
                if (A[i] > A[j]) return false;
        return true;
    }
}

class Solution:
    def isIdealPermutation(self, A: List[int]) -> bool:
        N = len(A)
        for i in range(N):
            for j in range(i + 2, N):
                if A[i] > A[j]:
                    return False
        return True

func isIdealPermutation(nums []int) bool {
    for i := 0; i < len(nums); i++ {
        if abs(nums[i]-i) > 1 {
            return false
        }
    }
    return true
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Algorithm

Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1.

Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии.

Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false.

😎