スタックの関連とtopK問題のJAVA実現

title:スタックの関連およびtopK問題のJAVA実装date:2020-03-09 21:03:42 tags:
スタックの関連
スタックとは

完全二叉木

各ノードの値は、その左右のサブノードに等しいか、またはそれ以下の値、すなわち、大きなトップスタックおよび小さなトップスタックである.

完全二叉木は配列を用いて格納されており,左右のポインタを用いる必要はなく,配列の下付きのみで左右サブノードにアクセスでき,0から計算を開始し,下付きiのノードの左ノードは2*i+1,右ノードは2*i+2である.
関連アクション
大きな天井を例にとると
ある配列要素をスタック化し、このノードからノードがその左右のサブノードの値より大きいまで:

    /**
     *   
     *
     * @param arr       
     * @param n          
     * @param i           
     */
    private static void heapify(int[] arr, int n, int i) {
        while (true) {
            //      
            int maxPos = i;
            //      （i * 2 + 1）  ，       
            if (i * 2 + 1 <= n && arr[i] < arr[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            //         （i * 2 + 2）  ，       
            if (i * 2 + 2 <= n && arr[maxPos] < arr[i * 2 + 2]) {
                maxPos = i * 2 + 2;
            }
            //             
            if (maxPos == i) {
                break;
            }
            //         
            swap(arr, i, maxPos);
            //                
            i = maxPos;
        }
    }

ビルド:

 /**
     *   
     *
     * @param arr
     */
    private void buildHeap(int[] arr) {
        // (arr.length - 1) / 2              
        //             ，         
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            heapify(arr, arr.length - 1, i);
        }
    }

ヒープのソート:

    /**
     *   
     * 

     *          0  
     *
     * @param arr
     */
    public void sort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }

        // 1、  
        buildHeap(arr);

        // 2、  
        int k = arr.length - 1;
        while (k > 0) {
            //      （  ）           
            swap(arr, 0, k);
            //          ，          
            heapify(arr, --k, 0);
        }
    }

ヒープ要素を削除し、最後のリーフノードをヒープの上に配置し、ヒープ化します.

    /**
     * @param arr 
     * @param n        
     */
    public void delTop(int[] arr , int n){
        if(n < 0) return;
        arr[0] = arr[n];
        heapify(arr , --n , 0);
    }

牛客には問題があり、最小のK個数を求めると、スタックを使って実現することができます.
タイトルの説明
n個の整数を入力し、その中で最も小さいK個の数を見つけます.例えば、4,5,1,6,2,7,3,8の8つの数字を入力すると、最小の4つの数字は>1,2,3,4である.
まず配列の前のK個の数を取り出して、大きなトップスタックを構築し、K+1番目の数からループを開始することができます.この数がトップ要素より小さい場合、この数をトップに置いてからスタック化します.
一次スタック化の時間的複雑度はO(logK)であり,配列O(n)を遍歴し,各要素がスタックに入ると仮定すると,時間的複雑度はO(nlongK)である.

    /**
     * @param k  top K  ，
     * @param a
     * @return
     */
    public int[] topK(int k , int[] a){
        int count = 0;
        int[] re = new int[k];
        for (int i = 0; i < k; i++) {
            re[i] = a[i];
        }
        //  K   
        for (int i = (k - 1) / 2; i >= 0; i--) {
            heapify(re, k-1, i);
        }
        
        for (int j = k; j < a.length; j++) {
            if(re[0] > a[j]){
                re[0] = a[j];
                heapify(re , re.length - 1 , 0);
            }
        }
        return re;
    }