c++

利用辅助空间，时间复杂度O(nlogk)

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result;
        if (input.size() < k) return result;
        multiset<int, greater<int> > intset;
        for (size_t i = 0; i < input.size(); ++ i) {
            if (intset.size()<k) intset.insert(input[i]);
            else {
                if (input[i] < *(intset.begin())) {
                    intset.erase(intset.begin());
                    intset.insert(input[i]);
                }
            }
        }
        for (auto iter = intset.begin(); iter != intset.end(); ++ iter) {
            result.push_back(*iter);
        }
        return result;
    }
};

利用二分思想

class Solution {
public:
    int partition(vector<int>& input, int left, int right) {
        int key = input[left];
        while(left < right) {
            while(left < right && input[right] > key) --right;
            input[left] = input[right];
            while(left < right && input[left] <= key) ++ left; 
            input[right] = input[left];
        }
        input[left] = key;
        return left;
    }

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result;
        if (input.size() <= 0 || k <= 0 || input.size() < k) return result;
        int left = 0, right = input.size()-1;
        int index = partition(input, left, right);
        while(index != k-1) {
            if (index < k - 1) left = index + 1;
            else right = index-1;
            index = partition(input, left, right);
        }
        for (int i = 0; i < k; ++ i) {
            result.push_back(input[i]);
        }
        return result;
    }
};