X個以上のX要素を持つ特別な配列Leetcodeソリューション


難易度 簡単に
よく聞かれる Google
配列 ハッシング

問題「Xより大きいか等しいX要素を持つ特別な配列」では、 配列 非負の整数の。 配列内にそれ以上のX要素が正確に存在するような整数Xを見つける必要があります。 この条件を満たす可能性のあるXがない場合は、-1を出力する必要があります。

1 2 3 4
-1
1 3 4 5
3

アプローチ(ブルートフォース)

解Xが存在する場合、 Xは常に一意になります。

証明:

X!= YとなるXNUMXつの解XとYがあるとします。X<Yと仮定します。ここで、X以上の要素の数は、解と見なすためXでなければなりません。 ただし、Y> Xであるため、X!= YとなるX以上のY要素があります。したがって、XとYが等しくない限り、Xが解であるという仮定は誤りです。

したがって、解決策が存在する場合、常に一意の解決策があります。 ここで、Xが解である場合、それ以上/等しい要素の数= Xであり、N未満である必要があります。ここで、N =配列のサイズ(可能な要素の最大数として) = N)。

したがって、解Xが存在する場合、それは [1、N]の範囲内にある必要があります。

範囲内の任意の整数以上である配列内の要素の数がその整数自体と等しいかどうか、範囲[1、N]内のすべての整数をチェックできます。 たとえば、Array = {1、3、4、5}について考えてみます。 これで、1と2には、それぞれ配列内でそれら以上の4と3の要素があります。 3以上の要素の数= 3。したがって、3が唯一の解決策です。 ツリー全体をトラバースして、[1、N]の範囲内のすべての整数よりも多い要素の数を見つけるため、このアプローチは低速です。

アルゴリズム

  1. i = 1からi = Nまでループを実行して、解を確認します。
    • '以上の要素の数を数えますi配列内の '
      • カウントが 'に等しい場合i'、iを返す
  2. 戻る -1;

XLeetcodeソリューション以上のX要素を持つ特別な配列の実装

C ++プログラム

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

int specialArray(vector <int> &a)
{
    int n = a.size() , counter = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        counter = 0;
        for(int j = 0 ; j < n ; j++)
            if(a[j] >= i)
                counter++;
        if(counter == i)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

Javaプログラム

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length , counter = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            counter = 0;
            for(int j = 0 ; j < n ; j++)
                if(a[j] >= i)
                    counter++;
            if(counter == i)
                return i;
        }
        return -1;
    }
}
3

X個以上のX要素を持つ特別な配列の複雑さの分析Leetcodeソリューション

時間の複雑さ

O(N * N)、N =配列のサイズ。 最悪の場合、X = Nが解である場合、O(N * N)の比較を行います。

スペースの複雑さ

O(1)。 一定のメモリスペースのみが使用されます。

アプローチ(最適)

配列を使用して、テーブル内のすべての要素の出現回数を格納できます。 値がNより大きい要素については、解の最大値がNになる可能性があるため、値Nの要素の出現としてカウントできることに注意してください。

ここで、X以上の要素の頻度= Xの頻度+ Xより大きいすべての要素の頻度。[1、N]の範囲内のすべての要素についてこれを見つけるには、接尾辞の頻度配列が必要です。 。

したがって、配列内のすべての整数について、設定する必要があります 頻度[i] =頻度[i] +頻度[i + 1]、 すべてのための 'i'範囲[N– 1、1]内。これにより、接尾辞頻度配列が作成され、以上の要素数が格納されます。 'i'  as 頻度[i]。

これで、ルックアップテーブルがあるため、[1、N]の範囲内の任意の整数の解を確認できます。 O(1) 時間。 これは私たちが トレード・オフ 時間通りに改善するためのメモリ。 テーブルのサイズはNなので、メモリ制限の心配もありません。

 

X個以上のX要素を持つ特別な配列Leetcodeソリューション

アルゴリズム

  1. 初期化   サイズNの配列で、各値は次のようになります。 ゼロ
  2. すべての要素について i  配列内:
    1. If i > N、増分周波数[N]
    2. 増分頻度[i]
  3. からサフィックス合計配列を作成します   として:
    1. からの範囲のすべての要素について i = N-1 〜へ i = 0
      1. セッションに 周波数[i] =頻度[i] +頻度[i + 1]
  4. からループを実行します i = 1に i = N
    1. If i ==頻度[i]、戻る i
  5. -1を返す

XLeetcodeソリューション以上のX要素を持つ特別な配列の実装

C ++プログラム

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

int specialArray(vector<int>& a)
{
    int n = a.size();
    vector <int> frequency(n + 1 , 0);
    for(int i = 0 ; i < n ; i++)
        if(a[i] > n)
            frequency[n]++;
        else
            frequency[a[i]]++;

    for(int i = n - 1 ; i >= 0 ; i--)
        frequency[i] += frequency[i + 1];

    for(int i = 0 ; i <= n ; i++)
        if(frequency[i] == i)
            return i;

    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

Javaプログラム

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length;
        int[] frequency = new int[n + 1];
        for(int i = 0 ; i < n ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < n ; i++)
            if(a[i] > n)
                frequency[n]++;
            else
                frequency[a[i]]++;

        for(int i = n - 1 ; i >= 0 ; i--)
            frequency[i] += frequency[i + 1];

        for(int i = 0 ; i <= n ; i++)
            if(frequency[i] == i)
                return i;

        return -1;
    }
}
3

X個以上のX要素を持つ特別な配列の複雑さの分析Leetcodeソリューション

時間の複雑さ

オン)、N =配列のサイズ。 O(1)時間で任意の整数をチェックできるため、最悪の場合、O(N)時間を使用します。

スペースの複雑さ

オン)。 線形メモリ空間は、周波数を格納するために使用されます。