[優先キュー][quick select]LeetCode面接問題40.最小k個数

[優先キュー][quick select]LeetCode面接問題40.最小k個数
整数配列arrを入力し、その中で最小のk個の数を見つけます.例えば、4、5、1、6、2、7、3、8の8つの数字を入力すると、最小の4つの数字は1、2、3、4です.
例1:

  ：arr = [3,2,1], k = 2
  ：[1,2]    [2,1]

例2:

  ：arr = [0,1,2,1], k = 1
  ：[0]

制限:

0 <= k <= arr.length <= 10000

0 <= arr[i] <= 10000

ゆうせんキュー
上から単調な列を考えて、間違っていることに気づいて、厳格に増加していないで、それからk個を挿入してから順番を並べたいと思って、それからできません.
知的障害者よ、優先列じゃないか、何ヶ月も触らないで何も忘れた
まず最初のk個の数を挿入してから、これと比較して、準備した数がスタックの数より小さい場合、スタックO(nlogk)をポップアップする.

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(k == 0) return vector<int> {};
        priority_queue<int> q;//     
        for(int i = 0; i < k; ++i) q.push(arr[i]);
        int n = arr.size();
        for(int i = k; i < n; ++i){
            if(arr[i] < q.top()) {
                q.pop();
                q.push(arr[i]);
            }
        }
        vector<int> res(k);
        for(int i = 0; i < k; ++i) {res[i] = q.top(); q.pop();}
        return res;
    }
};

公式にpythonの山があるのを見て、それは本当のストリームです.

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0: return []
        hp = [-x for x in arr[:k]]	#   k  ，      ，       
        heapq.heapify(hp)			#       
        for idx,num in enumerate(arr[k:]):
            if num < -hp[0]:
                heapq.heappop(hp)
                heapq.heappush(hp,-num)
        res = [-x for x in hp]
        return res

上はそれが流批ではないのは模倣で,下はこれが真滴流批である

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        return heapq.nsmallest(k,arr)	#   k     

quick select/クイック選択
クイックソート機能の活用
速い列はまず基礎要素tを探して、それから配列を左がtより小さくて、右がtより大きいように分割します
tの下付き文字がkに等しい場合、tの左側の要素は前のkの小さい要素である.
kより小さい場合は右側の区間を分け続けます
kより大きいと左の区間を区切る
速い列との違いは、処理するたびに片方だけを使う要素を早く選ぶことです.
注意選択時に選択するのは配列の下付き文字なので、パラメータを転送するときはkを1減算し、配列を返すときは1を加算します
所望時間複雑度はO(n)であり,最悪の場合の時間複雑度はO(n^2)である.

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(k == 0) return vector<int> {};
        return quickSearch(arr,0,arr.size() - 1, k - 1);//    1
    }

    vector<int> quickSearch(vector<int>& arr, int lo, int hi, int k){
        int idx = partition(arr,lo,hi);
        if(idx == k) return vector<int> (arr.begin(), arr.begin() + k + 1);//   1  
        return idx > k ? quickSearch(arr, lo, idx - 1, k) : quickSearch(arr, idx + 1, hi, k);
    }

    int partition(vector<int>& arr, int lo, int hi){
        int t = arr[lo], idx = lo;
        while(lo<hi){
            while(lo < hi && arr[hi] >= t) --hi;
            while(lo < hi && arr[lo] <= t) ++lo;
            if(lo>=hi) break;
            int temp = arr[hi];
            arr[hi] = arr[lo];
            arr[lo] = temp;
        }
        arr[idx] = arr[lo];
        arr[lo]  = t;
        return lo;
    }
};

カウントソート
本題のデータ範囲は限られているので,カウント順でもよい,時間的複雑度O(n)

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(k == 0) return vector<int> {};
        vector<int> count(10005,0);
        for(auto num:arr) ++count[num];
        vector<int> res(k);
        int t = 0;
        for(int i = 0; i < 10005; ++i) {
            while(count[i]-- > 0){
                if(t == k) break;
                res[t++] = i;
            }
        }
        return res;
    }
};