Java配列で上位K個の要素を検索する

投稿日: 2022-10-26 2022-10-26
タグ: Algorithms, Java Array

1. 概要

このチュートリアルでは、がJavaの配列でk個の最大要素を見つけるという問題に対するさまざまな解決策を実装します。時間計算量を説明するために、Big-O表記を使用します。

2. ブルートフォースソリューション

この問題に対するブルートフォースの解決策は、指定されたアレイをk回反復することです。 各反復で、最大値を見つけます。次に、この値を配列から削除して、出力リストに追加します。

public List findTopK(List input, int k) {
    List array = new ArrayList<>(input);
    List topKList = new ArrayList<>();

    for (int i = 0; i < k; i++) {
        int maxIndex = 0;

        for (int j = 1; j < array.size(); j++) {
            if (array.get(j) > array.get(maxIndex)) {
                maxIndex = j;
            }
        }

        topKList.add(array.remove(maxIndex));
    }

    return topKList;
}

n を指定された配列のサイズとすると、このソリューションの時間計算量はO（n * k）です。さらに、これは最も非効率的なソリューションです。

3. Javaコレクションアプローチ

ただし、この問題に対するより効率的な解決策が存在します。このセクションでは、Javaコレクションを使用してそのうちの2つについて説明します。

3.1. TreeSet

TreeSet には、バックボーンとして Red-Black Treeデータ構造があります。その結果、このセットに値を設定すると、 O（log n）のコストがかかります。 TreeSetはソートされたコレクションです。したがって、TreeSetにすべての値を入れてそれらの最初のkを抽出できます。

public List<Integer> findTopK(List<Integer> input, int k) {
    Set<Integer> sortedSet = new TreeSet<>(Comparator.reverseOrder());
    sortedSet.addAll(input);

    return sortedSet.stream().limit(k).collect(Collectors.toList());
}

このソリューションの時間計算量はO（n * log n）です。とりわけ、k≥logn の場合、これはブルートフォースアプローチよりも効率的であると考えられます。

TreeSetには重複が含まれていないことを覚えておくことが重要です。その結果、このソリューションは、異なる値を持つ入力配列に対してのみ機能します。

3.2. PriorityQueue

PriorityQueue は、Javaのヒープデータ構造です。その助けを借りて、 O（n * log k）ソリューションを実現できます。さらに、これは前のソリューションよりも高速なソリューションになります。上記の問題により、kは常にアレイのサイズよりも小さくなります。つまり、 O（n * log k）≤O（n * log n）。

アルゴリズムは、指定された配列を1回繰り返します。各反復で、ヒープに新しい要素を追加します。また、ヒープのサイズをk以下に保ちます。したがって、ヒープから余分な要素を削除して、新しい要素を追加する必要があります。その結果、配列を反復処理した後、ヒープにはkの最大値が含まれます。

public List<Integer> findTopK(List<Integer> input, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

    input.forEach(number -> {
        maxHeap.add(number);

        if (maxHeap.size() > k) {
            maxHeap.poll();
        }
    });

    List<Integer> topKList = new ArrayList<>(maxHeap);
    Collections.reverse(topKList);

    return topKList;
}

4. 選択アルゴリズム

与えられた問題を解決するための多くのアプローチがあります。また、このチュートリアルの範囲を超えていますが、選択アルゴリズムアプローチ を使用すると、線形の時間計算量が得られるため、が最適です。

5. 結論

このチュートリアルでは、配列内のk最大の要素を見つけるためのいくつかの解決策について説明しました。

いつものように、サンプルコードはGitHubでから入手できます。

getdocs

13036