top kアルゴリズムの説明

実際の作業では、長さnの配列の中で、前kの要素を探すことがよくあります.top kの問題に対して、最も暴力的な処理方法は、配列を直接並べ替えてから、前kの数字を切り取って、自分の目的を達成することです.このアルゴリズムの実現の複雑さはO(nlogn)です.実はO(n)のアルゴリズムやO(nlogk)時間の複雑さのアルゴリズムがあります.

高速配列のtopkアルゴリズムに基づいて高速並べ替えアルゴリズムを理解すれば、配列内のこの数より小さいすべての値を左側に、その数値より大きいすべての数を右側に置くという原理を知っています.したがってpartionを1回呼び出した後、その戻り値をpとすると、p番目の数字より小さいすべての数字が配列の左側にあり、p番目の数字より大きいすべての数字が配列の右側にある.高速配列の原理に基づいてtopkを探す要素を実現することができる.時間複雑度O(n)のコードを見た.

    private static int partion(int[] array, int low, int high) {

        int mid = array[low];
        while (low < high) {
            while (low < high && array[high] >= mid)
                high--;
            array[low] = array[high];
            while (low < high && array[low] <= mid)
                low++;
            array[high] = array[low];
        }
        array[low] = mid;
        return low;
    }

    private static int top_k(int[] array, int k) {

        if (array == null || array.length == 0)
            return -1;
        if (k < 0 || k > array.length - 1)
            return -1;
        int low = 0, high = array.length - 1;
        int index = partion(array, low, high);
        while (index != k) {
            if (index > k) {
                high = index - 1;
                index = partion(array, low, high);

            } else {
                low = index + 1;
                index = partion(array, low, high);
            }
        }
        return array[index];
    }

大トップスタックに基づくtopkアルゴリズムこのアルゴリズムは、大量のデータの場合に適しています.例えば、私たちが検索するデータが大きく、メモリを一度に全部読み込むことができない場合にも適しています.その原理を簡単に説明します.まずkの大きさの配列を作成して最小のk個の数字を格納し、次に入力したn個の数から1個の数を読み出し、容器がまだいっぱいでない場合は直接容器に挿入します.コンテナが満たされている場合は、コンテナの最大値と挿入する数値を比較する必要があります.挿入する数値がコンテナの最大値より小さい場合は、コンテナの最大値を削除し、新しい値を挿入する必要があります.そうしないと、処理は行われません.需要分析により,大天井は我々の需要を満たすことができることが分かったので,大天井によって我々の容器を実現し,そのコードは以下の通りであり,時間複雑度はO(nlogk)である.

    private final int MAXSIZE = 10 + 1;
    private int currentSize = 1;

    private void heap_insert(int[] array, int value) {

        if (currentSize < MAXSIZE) {
            array[currentSize++] = value;
            if (currentSize == MAXSIZE) {
                for (int i = currentSize / 2; i > 0; i--) {
                    heap_adjust(array, i, currentSize);
                }
            }
        } else {
            int max = array[1];
            if (value < max) {
                array[1] = value;
                heap_adjust(array, 1, currentSize);
            }
        }
    }

    //    
    private void heap_adjust(int[] array, int s, int len) {
        int temp = array[s];
        for (int i = 2 * s; i < len; i *= 2) {
            if (i < len - 1 && array[i] < array[i + 1])
                i++;
            if (array[i] <= temp)
                break;
            array[s] = array[i];
            s = i;
        }
        array[s] = temp;

    }

配列の0番目の要素は使用されていないことに気づくことができます.大きなトップスタックは完全な二叉木の原理に基づいて実現されるため、角標0は要素を格納することができません.具体的には、可視ソートアルゴリズムの文章のスタックソート部分を説明します.http://blog.csdn.net/dingpiao190/article/details/72674199
さらに、この大屋根のデータ構造は私たち自身が維持しています.Javaにとって、TreeSetは赤と黒の木に基づいて秩序化された集合であるため、JDKのTreeSet集合を直接利用して実現することができます.同様に,C++に対してset集合を用いて実現できる.JavaがTreeSetに基づいて実装するコードは以下の通りである.

private static TreeSet topk(int[] array, int n) {

        TreeSet set = new TreeSet();
        for (int i = 0; i < array.length; i++) {

            int value = array[i];
            if (set.size() < n)
                set.add(value);
            else {
                Iterator it = set.descendingIterator();
                int setMax = it.next();
                if (setMax > value ) {
                    it.remove();
                    set.add(value);
                }
            }
        }
        return set;

    }

,