アルゴリズム-TOpKに関する問題

アルゴリズム-TOpKに関する問題

1、1つの配列を与えて、その最大(小さい)K個の要素

を求めます

2、1つの配列を与えて、そのK番目の大きい数

を求めます

3、1つの配列を与えて中位数

を求める
TopK問題は面接でよく試験されたもので、実際の価値のあるアルゴリズムの中で代表的なもので、主な解決方法はスタック、迅速な選択、ソートの3つの案があります.次に、クラスをすばやく選択するアルゴリズムについて説明します.
1、一つの配列を与えて、その最大(小さい)K個の要素を求める
解題の構想は多種あって、例えば配列に対して並べ替えて、Arraysを使うことができます.sort();次に、前のK個の数、すなわち最小または最大のK個の数をとり、sortは昇順または降順で並ぶかを指定することができる.もちろん、時間の複雑さはNlog(N)で、確かに速いですが、面接官に鞭を打たれます.
実は彼らが試験したいのは山だけで、すべてNlog(N)ですが.スタックを用いてtopK問題の汎用解法を得ることができる.本題では、最大topK個数を例にとると、1、小さなスタックを構築することができ、スタック要素の数がK個未満の場合、直接スタックに入り、2、K個以上の場合、スタック上部と比較し、スタック上部より大きい場合、スタック上部をスタックし、スタック内の要素をすべてポップアップし、最大のK個数とする.
スタックは一般的に優先キューで実現されていることを知っていますが、JavaではPriorityQueueのデフォルトは小さなトップスタックです.

public int[] getTopK(int[] nums,int k){
	PriorityQueue<Integer> heap=new PriorityQueue<>();
	for(int i:nums){
		if(heap.size()<k){
			heap.offer(i);
		}else if(heap.top()<i){
			heap.poll();
			heap.offer(i);
		}
	}
	int [] result=new int[heap.size()];
	for(int i=0;i<result.length;i++){
		result[i]=heap.poll();
	}
	return result;
}

2、一つの配列を与えて、そのK番目の大きい数を求める
この問題と前の問題の違いは,本題が1つの数しか必要とせず,直接問題コードをはめ,弾き出す最初の数がK番目の数であることである.しかし、面接官は複雑度O(N)のアルゴリズムを書くように要求するかもしれませんが、問題の複雑度Nlog(N)、空間の複雑度kは使いにくいです.この時考察したのは実は1つの速い列の思想で、速い列にはもう1人の兄弟がいて、速い選択と呼ばれて、つまりquickSelectアルゴリズムで、時間の複雑さはO(N)まで下げることができます.速列はどうやって作ったか覚えていますか?ピボット・エレメントを選択します.1ラウンド後、左のエレメントはすべてピボット・エレメント以下、右のエレメントはすべてピボット・エレメント以上です.しかし,我々が探しているのは最小または最大のK番目の数であり,careの他の部分の値を全く使わず,ピボット要素の左半分または右半分の再帰的な高速選択だけを実現すればよい.迅速に選択した後、必要なデータは配列のk-1番目の要素です.

//   k       
public int getKthNumber(int nums[],int k){
	quickSelect(nums,0,nums.length-1,k);
	return nums[k-1];
}

private void quickSelect(int []nums,int left,int right,int k){
	if(left<right){
		int i=left,j=right;
		int privot=nums[left];//     
		while(i<j){
			while(i<j&&nums[j]>=privot){j--;}//            
			while(i<j&&nums[i]<=privot){i++;}//            
			if(i<j){
				swap(nums[i],i,j);
			}
		}
		swap(nums,left,i);//     
		if(k<=i){
			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;
}

3、一つの配列を与えて中位数を求める
この問題はスタックで実現するのも簡単で,配列サイズが奇数であれば,(配列長+1)/2のスタックを設定し,問題1に従ってスタックトップをポップアップするのが中位数である.偶数の場合は、配列長/2+1のサイズのスタックを設定し、2つの要素をポップアップして平均値を取ります.しかし、このような时间の复雑さはNlog(N)で、面接官は我慢できません...テーマ2の急速な選択の思想を思い付いて、私達はこのようにすることができます:1、配列の長さlenは奇数で、私達は2のコードを使って第(len+1)/2の小さい数を選んで、すなわち中位数2で、配列の長さlenは偶数で、私達は第len/2の小さい数と第len/2+1の小さい数を選んで、平均値を取って中位数です
あまり話さないで、直接コードを入れます.

    public void test(){
        int[] nums={3,5,1,6,7};
        if(nums.length%2==0){
            int k1=(nums.length+1)>>1;
            quickSelect(nums,k1);
            int a=nums[k1-1];
            int k2=(nums.length+1)>>1+1;
            quickSelect(nums,k2);
            int b=nums[k2-1];
            System.out.println((a+b)>>1);
        }else {
            int k=(nums.length+1)>>1;
            quickSelect(nums,k);
            System.out.println(nums[k-1]);
        }
    }

    public void quickSelect(int[] nums,int k){
        quickSelect(nums,0,nums.length-1,k);
    }


    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,left,i);
            if(k<=i){
                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;
    }