775. Global and Local Inversions

LeetCode medium original: C# #array #csharp #leetcode #medium
Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.
LeetCode Static

Дан tableau целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].

number глобальных инверсий — это количество различных пар (i, j), где:

0 <= i < j < n

nums[i] > nums[j]

number локальных инверсий — это количество индексов i, где:

0 <= i < n - 1

nums[i] > nums[i + 1]

return true, если количество глобальных инверсий равно количеству локальных инверсий.

Exemple:

Input: nums = [1,0,2]

Output: true

Explanation: There is 1 global inversion and 1 local inversion.

C# solution

correspondant/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

brouillon automatique, à relire avant soumission 
#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

correspondant/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

correspondant/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

correspondant/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

correspondant/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
}

Algorithm

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

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

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

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres
Il n'y a pas encore d'offres actives.