775. Global and Local Inversions

leetcode medium

#array#csharp#leetcode#medium

Task

Дан массив целых чисел 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.

C# solution

matched/original

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;
    }
}

C++ solution

auto-draft, review before submit

#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;
    }
}

Java solution

matched/original

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;
    }
}

JavaScript solution

matched/original

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;
    }
}

Python solution

matched/original

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

Go solution

matched/original

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
}

Explanation

Algorithm

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

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

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

😎