配列内で欠落している最小の整数を見つける

投稿日: 2022-10-29 2022-10-29
タグ: Core Java, Java, Java Array

1. 概要

このチュートリアルでは、配列内で欠落している最小の正の整数を見つけることができるさまざまなアルゴリズムを紹介します。

まず、問題の説明をします。その後、ニーズに合った3つの異なるアルゴリズムが表示されます。最後に、それらの複雑さについて説明します。

2. 問題の説明

まず、アルゴリズムの目的を説明しましょう。正の整数の配列で欠落している最小の正の整数を検索します。 つまり、x要素の配列で、配列にない0からx – 1までの最小要素を見つけます。配列にすべてが含まれている場合、解はx[X175Xです。 ]、配列サイズ。

たとえば、次の配列を考えてみましょう： [0、1、3、5、6]。 5要素があります。これは、この配列にない0と4の間の最小の整数を検索していることを意味します。この特定のケースでは、2です。

ここで、別の配列 [0、1、2、3]を想像してみましょう。 4 要素があるため、0と3の間の整数を検索しています。欠落しているものはないため、配列にない最小の整数は4です。

3. ソートされた配列

それでは、ソートされた配列で欠落している最小の数を見つける方法を見てみましょう。ソートされた配列では、欠落している最小の整数は、それ自体を値として保持しない最初のインデックスになります。

次のソートされた配列を考えてみましょう： [0、1、3、4、6、7]。次に、どの値がどのインデックスに一致するかを見てみましょう。

Index: 0 1 2 3 4 5
Value: 0 1 3 4 6 7

ご覧のとおり、値インデックスは整数 2 を保持していないため、2は配列内で欠落している最小の整数です。

このアルゴリズムをJavaに実装するのはどうですか？まず、メソッド searchInSortedArray（）を使用してクラスSmallestMissingPositiveIntegerを作成しましょう。

public class SmallestMissingPositiveInteger {
    public static int searchInSortedArray(int[] input) {
        // ...
    }
}

これで、配列を反復処理し、値としてそれ自体を含まない最初のインデックスを検索し、結果として返すことができます。

for (int i = 0; i < input.length; i++) {
    if (i != input[i]) {
        return i;
    }
}

最後に、欠落している要素を見つけずにループを完了した場合、インデックス 0 から開始するため、次の整数、つまり配列の長さを返す必要があります。

return input.length;

これがすべて期待どおりに機能することを確認しましょう。 0から5までの整数の配列で、3という数字が欠落していると想像してください。

int[] input = new int[] {0, 1, 2, 4, 5};

次に、最初に欠落している整数を検索すると、3が返されます。

int result = SmallestMissingPositiveInteger.searchInSortedArray(input);

assertThat(result).isEqualTo(3);

ただし、整数が欠落していない配列で欠落している数値を検索すると、次のようになります。

int[] input = new int[] {0, 1, 2, 3, 4, 5};

最初に欠落している整数は6であり、これは配列の長さです。

int result = SmallestMissingPositiveInteger.searchInSortedArray(input);

assertThat(result).isEqualTo(input.length);

次に、ソートされていない配列を処理する方法を説明します。

4. ソートされていない配列

では、ソートされていない配列で欠落している最小の整数を見つけるのはどうでしょうか。複数の解決策があります。 1つ目は、最初に配列を並べ替えてから、以前のアルゴリズムを再利用することです。別のアプローチは、別の配列を使用して存在する整数にフラグを立て、その配列をトラバースして最初の欠落している整数を見つけることです。

4.1. 配列を最初にソートする

最初のソリューションから始めて、新しい searchInUnsortedArraySortingFirst（）メソッドを作成しましょう。

したがって、アルゴリズムを再利用しますが、最初に、入力配列を並べ替える必要があります。これを行うには、 Arrays.sort（）を使用します。：

Arrays.sort(input);

このメソッドは、自然な順序に従って入力をソートします。整数の場合、それは最小のものから最大のものへを意味します。ソートアルゴリズムの詳細については、Javaでの配列のソートに関する記事を参照してください。

その後、ソートされた入力を使用してアルゴリズムを呼び出すことができます。

return searchInSortedArray(input);

これで、すべてが期待どおりに機能することを確認できます。ソートされていない整数と欠落している数値1および3を持つ次の配列を想像してみましょう。

int[] input = new int[] {4, 2, 0, 5};

1 は欠落している最小の整数であるため、メソッドを呼び出した結果であると予想されます。

int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input);

assertThat(result).isEqualTo(1);

それでは、番号が欠落していない配列で試してみましょう。

int[] input = new int[] {4, 5, 1, 3, 0, 2};

int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input);

assertThat(result).isEqualTo(input.length);

これで、アルゴリズムは 6 、つまり配列の長さを返します。

4.2. ブール配列の使用

もう1つの可能性は、入力配列と同じ長さの別の配列を使用することです。この配列は、 boolean 値を保持し、インデックスに一致する整数が入力配列で見つかったかどうかを示します。

まず、3番目のメソッド searchInUnsortedArrayBooleanArray（）を作成しましょう。

その後、ブール配列のインデックスに一致する入力配列の整数ごとに、ブール配列 flags 、およびを作成し、対応する値をtrueに設定します。

boolean[] flags = new boolean[input.length];
for (int number : input) {
    if (number < flags.length) {
        flags[number] = true;
    }
}

これで、 flags 配列は、入力配列に存在する整数ごとに true を保持し、それ以外の場合はfalseを保持します。次に、flags配列を反復して、falseを保持する最初のインデックスを返すことができます。ない場合は、配列の長さを返します。

for (int i = 0; i < flags.length; i++) {
    if (!flags[i]) {
        return i;
    }
}

return flags.length;

繰り返しになりますが、このアルゴリズムを例で試してみましょう。最初に、1と3が欠落しているアレイを再利用します。

int[] input = new int[] {4, 2, 0, 5};

次に、新しいアルゴリズムで欠落している最小の整数を検索すると、答えは1のままです。

int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input);

assertThat(result).isEqualTo(1);

そして、完全なアレイの場合、答えも変わらず、6のままです。

int[] input = new int[] {4, 5, 1, 3, 0, 2};

int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input);

assertThat(result).isEqualTo(input.length);

5. 複雑さ

アルゴリズムについて説明したので、 Big O表記を使用して、それらの複雑さについて説明しましょう。

5.1. ソートされた配列

入力がすでにソートされている最初のアルゴリズムから始めましょう。この場合、最悪のシナリオは、欠落している整数を検出しないため、配列全体をトラバースすることです。これは、線形の複雑さがあることを意味します。これは、 n が入力の長さであることを考慮すると、 O（n）と表記されます。

5.2. ソートアルゴリズムを使用したソートされていない配列

次に、2番目のアルゴリズムについて考えてみましょう。この場合、入力配列はソートされていないため、最初のアルゴリズムを適用する前にソートします。ここで、複雑さは、ソートメカニズムの複雑さとアルゴリズム自体の複雑さの間で最大になります。

Java 11以降、 Arrays.sort（）メソッドは、デュアルピボットクイックソートアルゴリズムを使用して配列をソートします。この並べ替えアルゴリズムの複雑さは、一般に O（n log（n））ですが、 O（n²）まで低下する可能性があります。つまり、アルゴリズムの複雑さは一般にO（n log（n））になり、O（n²）の2次の複雑さまで低下する可能性があります。

これは時間の複雑さのためですが、スペースを忘れないでください。検索アルゴリズムは余分なスペースを取りませんが、並べ替えアルゴリズムは余分なスペースを取ります。 クイックソートアルゴリズムの実行には最大O（log（n））スペースが必要です。これは、大規模な配列のアルゴリズムを選択するときに考慮したいことです。

5.3. ブール配列を使用したソートされていない配列

最後に、3番目で最後のアルゴリズムがどのように実行されるかを見てみましょう。これについては、入力配列をソートしません。つまり、ソートの複雑さに悩まされることはありません。実際のところ、両方とも同じサイズの2つの配列のみをトラバースします。つまり、時間計算量はO（2n）である必要があり、これはO（n）に簡略化されます。これは、以前のアルゴリズムよりも優れています。

ただし、スペースの複雑さに関しては、入力と同じサイズの2番目の配列を作成しています。これは、 O（n）スペースの複雑さがあることを意味します。これは、以前のアルゴリズムよりも劣っています。

それをすべて知っているので、それが使用される条件に応じて、私たちのニーズに最も適したアルゴリズムを選択するのは私たち次第です。

6. 結論

この記事では、配列内で欠落している最小の正の整数を見つけるためのアルゴリズムについて説明しました。ソートされた配列とソートされていない配列でこれを実現する方法を見てきました。また、さまざまなアルゴリズムの時間と空間の複雑さについても説明し、ニーズに応じて賢く選択できるようにしました。

いつものように、この記事に示されている完全なコード例は、GitHubでから入手できます。

getdocs

13036