5

私が考えているアルゴは

  • サイズ K の MaxHeap を保持する
  • 各要素を挿入する
  • ヒープがいっぱいの場合は小さい値を削除
  • 結局、Kth max は MaxHeap の小さい方です

それは私にO（NlogK）を与えるでしょう。より良いアルゴリズムはありますか？配列をメモリに保存できないため、クイック選択を行うことができません。

4

5 に答える 5

11

メモリの制限に応じて、中央値の中央値アルゴリズムの修正版を使用して、O(n) 時間と O(k) 空間で問題を解くことができます。

考え方は以下の通りです。サイズ 2k の配列をメモリに保持します。このバッファーに配列の最初の 2k 要素を入力し、中央値アルゴリズムを実行して、最大の k 要素を配列の前半に配置し、最小の k 要素を配列の後半に配置します。次に、最小の k 個の要素を破棄します。次に、次の k 個の要素を配列の後半にロードし、median-of-medians アルゴリズムを使用して、上部の k 個の要素を左側に、下部の k 個の要素を右側に配置します。配列全体でこのプロセスを繰り返すと、バッファーの後半を配列の次の k 個の要素に置き換え、median-of-medians を使用してそれらの上位 k 個を左半分に移動すると、最後に配列の左半分に上位 k 個の要素があります。

全体として、サイズ O(k) の配列を使用して median-of-medians アルゴリズムに O(n / k) 呼び出しを行うことになります。これは、O(k) 時間かかるアルゴリズムへの O(n / k) 呼び出しです。 、O(n) の正味ランタイムの場合。これを最終ステップと組み合わせると、O(n + k) = O(n) 時間で実行されます。さらに、median-of-medians ステップのメモリ使用量は O(k) であり、サイズ O(k) のバッファが存在するため、これは O(k) メモリのみを使用します。つまり、最小ヒープ ソリューションよりも漸近的に高速であり、メモリ内で漸近的に同等です。

お役に立てれば！

于 2011-06-22T21:43:10.530 に答える
1

これはhttp://en.wikipedia.org/wiki/Selection_algorithmとして知られています

特に 1 つのアルゴリズムはhttp://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithmです。

O(N)時間と空間O(1)です。配列がソートされていない場合は、インプレースで実行できると思います。アレイが外部 (ハードディスク、ネットワークなど) に保存されている~K場合は、作業に必要な言葉を活用できます。配列が関数によって動的に生成される場合、同様の状況になります。

于 2011-06-22T21:36:23.547 に答える
0

PriorityQueue を使用した実装があります。これを試して：

import java.util.PriorityQueue;

public class FindKthLargestElementWithHeap {

    /**
     * We can use a min heap to solve this problem. 
     * The heap stores the top k elements.
     * Whenever the size is greater than k, delete the min.
     * Time complexity is O(nlog(k)).
     * Space complexity is O(k) for storing the top k numbers.
     */
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>(k);
        for(int i: nums){
            q.offer(i);

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

        return q.peek();
    }

    public static void main(String args[]) {
        int[] nums = {5,8,6,97,12,3,5,6,4,2,3,};
        //Return the second largest number
        System.out.println(findKthLargest(nums,2));
    }

}

詳細については、https ://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/FindKthLargestElementWithHeap.java にアクセスしてください。

于 2016-09-19T20:28:20.550 に答える
0

maxheap は効率的な「最小値の検索」をサポートしていないため、アルゴリズムをわずかに変更します。

  • 最初の K 個のアイテムを最小ヒープに挿入する

  • 残りの項目については、値がヒープヘッドより大きい場合

    • 頭をポップし、新しいアイテムを挿入します。

  • 頭は K 番目に大きい項目です。

最悪のケースは、各項目が最後の K の最小値よりも大きい入力の場合でも O(N lg K) です。アイテム。

于 2011-06-22T21:39:18.430 に答える
0

このコードを実行しました-要素の位置に触れたり、同じものを並べ替えたりすることなく、正常に実行されました。

public class nth {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        calc.getit(2);
    }

}
class calc{
    static int arr[] = { 1, 23, 47, 81, 92, 87, 52, 48, 56, 66, 65, 76, 71, 85,
        49, 53, 56, 61, 65, 84 };

    static void getit(int k){
        int i,j=0;
        for(i=0;i<arr.length;i++){
            int c=0;
            for(j=0;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    c++;
                }
            }
            if(c==k-1){
                System.out.println(arr[i]);
            }
        }
    }
}
于 2014-04-27T08:56:25.377 に答える