775. Global and Local Inversions

LeetCode medium original: C# #array #csharp #leetcode #medium
選択した UI 言語に合わせて問題文をロシア語から翻訳します。コードは変更しません。
LeetCode Static

Дан 配列 целых чисел 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, если количество глобальных инверсий равно количеству локальных инверсий.

例:

Input: nums = [1,0,2]

Output: true

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

C# 解法

照合済み/オリジナル 
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++ 解法

自動ドラフト、提出前に確認 
#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 解法

照合済み/オリジナル 
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 解法

照合済み/オリジナル 
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 解法

照合済み/オリジナル 
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 解法

照合済み/オリジナル 
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.

😎

Vacancies for this task

有効な求人 with overlapping task tags are 表示.

すべての求人
有効な求人はまだありません。