アルゴリズム-再探無秩序配列の中央値の問題

アルゴリズム-再探無秩序配列の中央値の問題

アルゴリズム-再探無秩序配列の中央値問題

アルゴリズム-再探無秩序配列の中央値の問題
無秩序配列を指定します.無秩序配列の中央値を求めます.
この問題は前に書いたブログでアルゴリズム-TopKに関する問題を述べました.ヒープで実現できます.あるいは、高速選択アルゴリズムで実現できます.高速選択アルゴリズムを使用して実装する場合、2つのケースに分けて議論します.1つは配列要素の数が奇数の場合、直接中間要素を選択すればいいです.もう一つは偶数の場合、2回のクイック選択をします.
しかし、上記の方法では、配列要素の数が偶数の場合、配列に対する最初の迅速な選択の影響には注目しておらず、第二の高速選択の時間的複雑さはO(N^2)に達する可能性がある.
実際には、私たちは速い選択の性質を利用して、第二の選択時間の複雑さをO(k-1)に低減することができます.
迅速な選択の原理は、ハブを位置k-1に調整し、最終的には、ハブの左側の要素は、ハブの要素に等しいものよりも大きく、右の要素は、ハブの要素に等しいものよりも小さい、または逆です.
k番目の大きさの元素を選ぶ時、実際には、k-1の大きい元素が中枢の左半分または右半分にあることを確認できます.
K番目の大きさの要素を選択する例として、配列を降順で選択します.
1、配列長が偶数の場合は、nums.length/2＋1の大きな要素(m 1と表記)とnums.length/2の大きい要素(m 2と表記)を選択する必要があります.m 1を選択すれば、m 2はk-1の左半分にあり、左半分は全部m 1より大きいので、問題は[0,k-1]区間の最小値、つまりm 2になります.直接に遍歴した範囲の元素は最小値m 2を探せばいいです.最終的な結果は(m 1+m 2)/2です.
2、配列長が奇数の時、私達は直接に第nums.length/2+1の大きい要素を選択します.m 1は私達が探している中央の桁です.
このように、私達はより速くて簡単なコードを得ることができます.

    @Test
    public void test(){
        int[] nums={7,5,9,3,11,32,27,1,-9,4};
        //-9,1,3,4,5,7,9,11,27,32
        System.out.println(mediumNUmberOfMixArray(nums));
    }


    public int mediumNUmberOfMixArray(int[] nums){
        int k=nums.length/2+1;
        quickSelect(nums,0,nums.length-1,k);
        int m1=nums[k-1];
        if(nums.length%2==1){
            return m1;
        }else {
            int m2=Integer.MAX_VALUE;
            for (int i=0;i<k-1;i++){
                m2=Math.min(m2,nums[i]);
            }
            return (m1+m2)/2;
        }

    }
    public void quickSelect(int[] nums,int left,int right,int k){
        if(left<right){
            int i=left,j=right;
            int pivot=nums[left];
            while (i<j){
                while (i<j&&nums[j]<=pivot){
                    j--;
                }
                while (i<j&&nums[i]>=pivot){
                    i++;
                }
                if(i<j){
                    swap(nums,i,j);
                }
            }
            swap(nums,i,left);//     
            if(i>=k){
                quickSelect(nums,left,i-1,k);
            }else {
                quickSelect(nums,i+1,right,k);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }