1. 序章

この記事では、2つのソートされた配列の和集合でk番目に小さい要素を見つける方法を説明します。

まず、正確な問題を定義します。 次に、2つの非効率的ですが簡単な解決策があります。 第三に、2つの配列の二分探索に基づく効率的なソリューションを見ていきます。 最後に、アルゴリズムが機能することを確認するためのいくつかのテストを見ていきます。

アルゴリズムのすべての部分のJavaコードスニペットも表示されます。 簡単にするために、実装は整数でのみ動作します。 ただし、説明されているアルゴリズムは、比較可能なすべてのデータ型で機能し、ジェネリックスを使用して実装することもできます。

2. 2つのソートされた配列の和集合でK番目に小さい要素は何ですか?

2.1. K番目に小さい要素

k 番目に小さい要素( k 次の統計とも呼ばれる)を配列内で見つけるには、通常、選択アルゴリズムを使用します。 ただし、これらのアルゴリズムは単一のソートされていない配列で動作しますが、この記事では、2つのソートされた配列でk番目に小さい要素を見つけたいと考えています。

問題のいくつかの解決策を見る前に、達成したいことを正確に定義しましょう。 そのために、すぐに例に飛び込みましょう。

2つのソートされた配列(ab)が与えられますが、これらは必ずしも同じ数の要素を持つ必要はありません。

これらの2つの配列で、k番目に小さい要素を見つけます。 具体的には、結合およびソートされた配列でk番目に小さい要素を見つけます。

この例の結合およびソートされた配列を(c)に示します。 1stの最小要素は3であり、4thの最小要素は20です。

2.2. 重複する値

また、重複する値を処理する方法を定義する必要があります。 要素は、配列の1つ(aの要素3)で複数回発生する可能性があり、2番目の配列( b )でも再び発生する可能性があります。

重複を1回だけカウントする場合は、(c)に示すようにカウントします。 要素のすべての出現をカウントする場合、(d)に示すようにカウントします。

この記事の残りの部分では、(d)に示すように重複をカウントし、別個の要素であるかのようにカウントします。

3. 2つの単純だが効率の悪いアプローチ

3.1. 2つの配列を結合してから並べ替える

k 番目に小さい要素を見つける最も簡単な方法は、配列を結合して並べ替え、結果の配列のk番目の要素を返すことです。

int getKthElementSorted(int[] list1, int[] list2, int k) {

    int length1 = list1.length, length2 = list2.length;
    int[] combinedArray = new int[length1 + length2];
    System.arraycopy(list1, 0, combinedArray, 0, list1.length);
    System.arraycopy(list2, 0, combinedArray, list1.length, list2.length);
    Arrays.sort(combinedArray);

    return combinedArray[k-1];
}

n が最初の配列の長さであり、mが2番目の配列の長さである場合、結合された長さ c = n +mが得られます。

ソートの複雑さはO(c log c)であるため、このアプローチの全体的な複雑さは O(n log n)です。

このアプローチの欠点は、アレイのコピーを作成する必要があることです。これにより、より多くのスペースが必要になります。

3.2. 2つのアレイをマージする

マージソートソートアルゴリズムの1つのステップと同様に、2つの配列をマージしてから、k番目の要素を直接取得できます。

マージアルゴリズムの基本的な考え方は、1番目と2番目の配列の最初の要素を指す2つのポインターから始めることです(a)。

次に、ポインターで2つの要素(34)を比較し、小さい方の要素( 3 )を結果に追加して、そのポインターを1つの位置に移動します。フォワード(b)。 ここでも、ポインターの要素を比較し、小さい方の要素( 4 )を結果に追加します。

結果の配列にすべての要素が追加されるまで、同じ方法で続行します。 入力配列の1つにそれ以上の要素がない場合は、他の入力配列の残りのすべての要素を結果配列にコピーするだけです。

完全な配列をコピーしないとパフォーマンスを向上させることができますが、結果の配列にk要素が含まれると停止します。 結合されたアレイ用に追加のアレイを作成する必要はありませんが、元のアレイでのみ操作できます。

Javaの実装は次のとおりです。

public static int getKthElementMerge(int[] list1, int[] list2, int k) {

    int i1 = 0, i2 = 0;

    while(i1 < list1.length && i2 < list2.length && (i1 + i2) < k) {
        if(list1[i1] < list2[i2]) {
            i1++;
        } else {
            i2++;
        }
    }

    if((i1 + i2) < k) {
        return i1 < list1.length ? list1[k - i2 - 1] : list2[k - i1 - 1]; 
    } else if(i1 > 0 && i2 > 0) {
        return Math.max(list1[i1-1], list2[i2-1]);
    } else {
        return i1 == 0 ? list2[i2-1] : list1[i1-1];
    }
}

このアルゴリズムの時間計算量がO( k )であることを理解するのは簡単です。 このアルゴリズムの利点は、重複する要素を1回だけ考慮するように簡単に適応できることです

4. 両方の配列の二分探索

O( k )よりもうまくいくことができますか? 答えはできるということです。 基本的な考え方は、2つのアレイに対してバイナリ検索アルゴリズムを実行することです

これを機能させるには、すべての要素への一定時間の読み取りアクセスを提供するデータ構造が必要です。 Javaでは、それは配列またはArrayListである可能性があります。

実装するメソッドのスケルトンを定義しましょう。

int findKthElement(int k, int[] list1, int[] list2)
    throws NoSuchElementException, IllegalArgumentException {

    // check input (see below)

    // handle special cases (see below)

    // binary search (see below)
}

ここでは、kと2つの配列を引数として渡します。 まず、入力を検証します。 次に、いくつかの特殊なケースを処理してから、バイナリ検索を実行します。 次の3つのセクションでは、これらの3つのステップを逆の順序で見ていきます。したがって、最初に2分探索、次に特殊なケース、最後にパラメーターの検証について説明します。

4.1. 二分探索

特定の要素を検索する標準の二分探索では、2つの結果が考えられます。探している要素が見つかって検索が成功するか、見つからずに検索が失敗するかのいずれかです。 これは、k番目に小さい要素を見つけたい場合とは異なります。 ここでは、常に結果があります。

それを実装する方法を見てみましょう。

4.1.1. 両方の配列から正しい数の要素を見つける

最初の配列の特定の数の要素から検索を開始します。 その番号をnElementsList1と呼びましょう。 合計でk要素が必要なため、nElementsList1の数は次のようになります。

int nElementsList2 = k - nElementsList1;

例として、 k =8としましょう。 最初の配列の4つの要素と、2番目の配列の4つの要素から始めます(a)。

最初の配列の4番目の要素が2番目の配列の4番目の要素よりも大きい場合、最初の配列から取得した要素が多すぎて、 nElementsList1 を減らすことができます(b)。 それ以外の場合は、取得した要素が少なすぎるため、 nElementsList1 (b’)を増やすことができます。

停止基準に達するまで続行します。 それが何であるかを見る前に、これまでに説明したことのコードを見てみましょう。

int right = k;
int left = = 0;
do {
    nElementsList1 = ((left + right) / 2) + 1;
    nElementsList2 = k - nElementsList1;

    if(nElementsList2 > 0) {
        if (list1[nElementsList1 - 1] > list2[nElementsList2 - 1]) {
            right = nElementsList1 - 2;
        } else {
            left = nElementsList1;
        }
    }
} while(!kthSmallesElementFound(list1, list2, nElementsList1, nElementsList2));

4.1.2. 停止基準

2つの場合で停止できます。 まず、最初の配列から取得する最大要素が2番目の配列から取得する最大要素と等しい場合に停止できます(c)。 この場合、その要素を単純に返すことができます。

次に、次の2つの条件が満たされた場合に停止できます(d)。

  • 最初の配列から取得する最大の要素は、2番目の配列から取得しない最小の要素よりも小さくなります( 11 <100 )。
  • 2番目の配列から取得する最大の要素は、最初の配列から取得しない最小の要素よりも小さくなります( 21 <27 )。

その条件が機能する理由を視覚化するのは簡単です(d’)。2つの配列から取得するすべての要素は、2つの配列の他の要素よりも確かに小さいです。

停止基準のコードは次のとおりです。

private static boolean foundCorrectNumberOfElementsInBothLists(int[] list1, int[] list2, int nElementsList1, int nElementsList2) {

    // we do not take any element from the second list
    if(nElementsList2 < 1) {
        return true;
    }

    if(list1[nElementsList1-1] == list2[nElementsList2-1]) {
        return true;
    }

    if(nElementsList1 == list1.length) {
        return list1[nElementsList1-1] <= list2[nElementsList2];
    }

    if(nElementsList2 == list2.length) {
        return list2[nElementsList2-1] <= list1[nElementsList1];
    }

    return list1[nElementsList1-1] <= list2[nElementsList2] && list2[nElementsList2-1] <= list1[nElementsList1];
}

4.1.3. 戻り値

最後に、正しい値を返す必要があります。 ここでは、次の3つのケースが考えられます。

  • 2番目の配列から要素を取得しないため、ターゲット値は最初の配列にあります(e)
  • ターゲット値は最初の配列(e’)にあります
  • ターゲット値は2番目の配列(e “)にあります

これをコードで見てみましょう:

return nElementsList2 == 0 ? list1[nElementsList1-1] : max(list1[nElementsList1-1], list2[nElementsList2-1]);

最初の配列から要素を取得しない場合を処理する必要がないことに注意してください。後で特別な場合の処理でその場合を除外します。

4.2. 左右の境界線の初期値

これまで、最初の配列の左右の境界線をk0で初期化しました。

int right = k;
int left = 0;

ただし、 k の値によっては、これらの境界線を調整する必要があります。

まず、 k が最初の配列の長さを超える場合、最後の要素を右の境界線と見なす必要があります。 配列から多くの要素を取得することはできないため、この理由は非常に単純です。

次に、 k が2番目の配列の要素数よりも大きい場合、最初の配列から少なくとも(k – length(list2))を取る必要があることがわかります。配列。 例として、 k =7としましょう。 2番目の配列には4つの要素しかないため、最初の配列から少なくとも 3 要素を取得する必要があることがわかっているため、 L2:に設定できます。 ]

適合した左右の境界線のコードは次のとおりです。

// correct left boundary if k is bigger than the size of list2
int left = k < list2.length ? 0 : k - list2.length - 1;

// the inital right boundary cannot exceed the list1
int right = min(k-1, list1.length - 1);

4.3. 特別な場合の取り扱い

実際の二分探索を行う前に、いくつかの特殊なケースを処理して、アルゴリズムの複雑さを少し軽減し、例外を回避することができます。 コメントに説明が含まれるコードは次のとおりです。

// we are looking for the minimum value
if(k == 1) {
    return min(list1[0], list2[0]);
}

// we are looking for the maximum value
if(list1.length + list2.length == k) {
    return max(list1[list1.length-1], list2[list2.length-1]);
}

// swap lists if needed to make sure we take at least one element from list1
if(k <= list2.length && list2[k-1] < list1[0]) {
    int[] list1_ = list1;
    list1 = list2;
    list2 = list1_;
}

4.4. 入力検証

最初に入力検証を見てみましょう。 たとえば、 NullPointerExceptionまたはArrayIndexOutOfBoundsException、などのアルゴリズムが失敗してスローされるのを防ぐために、3つのパラメーターが次の条件を満たすことを確認する必要があります。

  • 両方の配列はnullであってはならず、少なくとも1つの要素を持っている必要があります
  • k>=0 である必要があり、2つのアレイを合わせた長さより大きくすることはできません。

コードでの検証は次のとおりです。

void checkInput(int k, int[] list1, int[] list2) throws NoSuchElementException, IllegalArgumentException {

    if(list1 == null || list2 == null || k < 1) { 
        throw new IllegalArgumentException(); 
    }
 
    if(list1.length == 0 || list2.length == 0) { 
        throw new IllegalArgumentException(); 
    } 

    if(k > list1.length + list2.length) {
        throw new NoSuchElementException();
    }
}

4.5. 完全なコード

これが今説明したアルゴリズムの完全なコードです:

public static int findKthElement(int k, int[] list1, int[] list2) throws NoSuchElementException, IllegalArgumentException {

    checkInput(k, list1, list2);

    // we are looking for the minimum value
    if(k == 1) {
        return min(list1[0], list2[0]);
    }

    // we are looking for the maximum value
    if(list1.length + list2.length == k) {
        return max(list1[list1.length-1], list2[list2.length-1]);
    }

    // swap lists if needed to make sure we take at least one element from list1
    if(k <= list2.length && list2[k-1] < list1[0]) {
        int[] list1_ = list1;
        list1 = list2;
        list2 = list1_;
    }

    // correct left boundary if k is bigger than the size of list2
    int left = k < list2.length ? 0 : k - list2.length - 1; 

    // the inital right boundary cannot exceed the list1 
    int right = min(k-1, list1.length - 1); 

    int nElementsList1, nElementsList2; 

    // binary search 
    do { 
        nElementsList1 = ((left + right) / 2) + 1; 
        nElementsList2 = k - nElementsList1; 

        if(nElementsList2 > 0) {
            if (list1[nElementsList1 - 1] > list2[nElementsList2 - 1]) {
                right = nElementsList1 - 2;
            } else {
                left = nElementsList1;
            }
        }
    } while(!kthSmallesElementFound(list1, list2, nElementsList1, nElementsList2));

    return nElementsList2 == 0 ? list1[nElementsList1-1] : max(list1[nElementsList1-1], list2[nElementsList2-1]);
}

private static boolean foundCorrectNumberOfElementsInBothLists(int[] list1, int[] list2, int nElementsList1, int nElementsList2) {

    // we do not take any element from the second list
    if(nElementsList2 < 1) {
        return true;
    }

    if(list1[nElementsList1-1] == list2[nElementsList2-1]) {
        return true;
    }

    if(nElementsList1 == list1.length) {
        return list1[nElementsList1-1] <= list2[nElementsList2];
    }

    if(nElementsList2 == list2.length) {
        return list2[nElementsList2-1] <= list1[nElementsList1];
    }

    return list1[nElementsList1-1] <= list2[nElementsList2] && list2[nElementsList2-1] <= list1[nElementsList1];
}

5. アルゴリズムのテスト

GitHubリポジトリには、多くの可能な入力配列と多くのコーナーケースをカバーする多くのテストケースがあります。

ここでは、静的入力配列に対してではなく、ダブルバイナリ検索アルゴリズムの結果を単純な結合および並べ替えアルゴリズムの結果と比較するテストの1つのみを指摘します。 入力は、2つのランダム化された配列で構成されます。

int[] sortedRandomIntArrayOfLength(int length) {
    int[] intArray = new Random().ints(length).toArray();
    Arrays.sort(intArray);
    return intArray;
}

次のメソッドは、1つのテストを実行します。

private void random() {

    Random random = new Random();
    int length1 = (Math.abs(random.nextInt())) % 1000 + 1;
    int length2 = (Math.abs(random.nextInt())) % 1000 + 1;

    int[] list1 = sortedRandomIntArrayOfLength(length1);
    int[] list2 = sortedRandomIntArrayOfLength(length2);

    int k = (Math.abs(random.nextInt()) + 1) % (length1 + length2);

    int result = findKthElement(k, list1, list2);
    int result2 = getKthElementSorted(list1, list2, k);
    int result3 = getKthElementMerge(list1, list2, k);

    assertEquals(result2, result);
    assertEquals(result2, result3);
}

そして、上記のメソッドを呼び出して、次のような多数のテストを実行できます。

@Test
void randomTests() {
    IntStream.range(1, 100000).forEach(i -> random());
}

6. 結論

この記事では、2つのソートされた配列の和集合でk番目に小さい要素を見つける方法をいくつか見てきました。 最初に、単純で単純な O(n log n)アルゴリズム、次に複雑なバージョン O(n)、最後にOで実行されるアルゴリズムを見ました。 (log n)

私たちが最後に見たアルゴリズムは、優れた理論的演習です。 ただし、ほとんどの実用的な目的では、最初の2つのアルゴリズムのいずれかを使用することを検討する必要があります。これは、2つの配列に対する二分探索よりもはるかに単純です。 もちろん、パフォーマンスが問題になる場合は、バイナリ検索が解決策になる可能性があります。

この記事のすべてのコードは、GitHubでから入手できます。