欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode-面试题40. 最小的k个数

程序员文章站 2024-03-15 09:08:35
...

面试题40. 最小的k个数

LeetCode-面试题40. 最小的k个数

方法一:暴力法
直接排序

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        vector<int>ret(arr.begin(), arr.begin() + k);
        return ret;
    }
};

方法二:堆
利用大根堆来找Top k

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

        return ret;
    }
};

方法三:快排
利用快速排序思想实现快速查找

class Solution {
    int partition(vector<int>& nums, int left, int right) {
        int v = nums[left];
        int i = left, j = right + 1;
        while (true) {
            while (++i <= right && nums[i] < v);
            while (--j >= left && nums[j] > v);
            if (i >= j) {
                break;
            }
            swap(nums[i], nums[j]);
        }
        swap(nums[j], nums[left]);

        return j;
    }
    vector<int> quickSearch(vector<int>& nums, int left, int right, int k) {
        int i = partition(nums, left, right);
        if (i == k) {
            vector<int>ret(nums.begin(), nums.begin() + k + 1);

            return ret;
        }
        return i > k ? quickSearch(nums, left, i - 1, k) : quickSearch(nums, i + 1, right, k);
    }
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k == 0) {
            vector<int>ret(k, 0);
            return ret;
        }
        return quickSearch(arr, 0, arr.size() - 1, k - 1);//数组的第k-1位
    }
};
相关标签: LeetCode