K最小

久しぶりに問題を切って、c++文法はほとんど忘れていません....いくつかの問題を探して手の前の問題を練習してgithubを解放して、後で更に問題を切って、できるだけ両側にすべて置くようにしましょう部分leetcodeの問題を切って解きます

テーマ大意:与えられたデータは前K小

を求めます

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(k > input.size() || k == 0 || input.size() == 0 ) return  vector<int>();
        make_heap(input.begin(),input.begin()+k);
        while(k < input.size()){
            if(input[k] < input[0]){
                input[0] = input[k];
                make_heap(input.begin(),input.begin()+k);
            }
            input.erase(input.begin()+k);
        }
        return input;
    }
};

テーマリンクpartition思想に基づく解法
今のところ、最良の状況でも全量のデータを走りながら走らなければなりません.つまり、複雑度O(n)私のところではmake_を使っています....eraseのちょっと騒がしい操作.のmake_Heapの本質:シーケンステーブルのシフトはスタックを構成し、下層は依然としてシーケンステーブルvectorである.eraseはsizeの変化をもたらし、反復器の失効を引き起こすので注意が必要です