最小的K個數 (冒泡和最小堆）

問題：最小的K個數

輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。

方法一（冒泡排序k趟）

思路：冒泡排序進行k趟即可，就把最小的k個跳出來了

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        int len = input.size();
        if(len == k )
            return input;
        if(k>len || k<=) //注意判斷條件
            return res;

        //冒泡前k趟即可
        for(int i = ;i<k;i++)
            {
            for(int j = len-;j>i;j--)
                {
                if(input[j] < input[j-])
                    {
                    int temp = input[j];
                    input[j] = input[j-];
                    input[j-] = temp;
                }
            }
            res.push_back(input[i]); //放在這兒就行拉，何必再做一遍          
        }

        //思路是這麼走的，但是寫完後還是要看看怎麼簡化代碼的
        //for(int i =0;i<k;i++)
            //{
          //  res.push_back(input[i]);
        //}
        return res;
    }
};
           

方法二：堆排序

思路：使用簡單粗暴的全部排序的方法并不能取得很好的性能隻要求k個數，是以使用最小堆就可以了。(如果是要取最大值就是用最大堆）

class Solution {
private:
     void heapSort(vector<int> &input, int root, int end){
        for(int j = end -; j >= root; j --){
            int parent = (j + root -)/;
            if(input[parent] > input[j]){
                int temp = input[j];
                input[j] = input[parent];
                input[parent] = temp;
            }
        }   
     }

public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result ;
        if(k > input.size()) return result;
        for(int i = ; i < k ; i ++){
            heapSort(input,i,input.size());
            result.push_back(input[i]);
        }
        return result;
    }
};
           

歡迎補充更好的方法

未完待續。。。。。。。。。。。