【剑指Offer】T40 最小的K个数

输入 n 个整数,找出其中最小的 K 个数。例如输入 4,5,1,6,2,7,3,8 这 8 个数字,则最小的 4 个数字是 1,2,3,4,。

思路 1:快排思想,对原数组进行调整

  • 选取A[0]作枢纽值index,调整
  • 当枢纽index不为k-1 时,继续调整(数组下标 0 开始)
    • index大于 k-1 ,高指针下移,调整
    • index小于 k-1 ,低指针上移,调整
  • 调整后截取 0k,即为最后结果

代码:

class Solution {
public:
    int Partition(vector<int>& A, int low, int high){
        
        int pivot = A[low];
        while(low < high){
            while (low < high && A[high] >= pivot)
                high--;
            A[low] = A[high];
            while(low < high && A[low] <= pivot)
                low++;
            A[high] = A[low];
        }
        A[low] = pivot;
        return low;
    }
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len = input.size();
    
        if(len == 0 || k > len || k <= 0)
            return vector<int>();
        if(len == k)
            return input;

        int low = 0;
        int high = len - 1;
        int pivot = Partition(input, low , high);
        while(pivot != k-1){
            if(pivot > k-1){
                high = pivot - 1;
                pivot = Partition(input, low, high);
            }else{
                low = pivot + 1;
                pivot = Partition(input, low, high);
            }
        }
        vector<int> res(input.begin(), input.begin() + k);
        return res;
    }
};

快排应该信手拈来

思路 2:全排序,直接用sort(),再输出前 k

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    if(input.empty() || k > input.size())
        return vector<int>();
    
    sort(input.begin(), input.end());
    vector<int> res(input.begin(), input.begin()+k);
    return res;
}

本文链接:https://ariser.cn/index.php/archives/389/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!