剑指offer 最小的k个数

男娘i 2022-06-08 09:38 173阅读 0赞

# 1.题目描述 #

输入n个数字，找出其中最小的k个数。

注：有的还会要求保持原有的顺序输出

# 2.分析 #

两种思路：  
1）利用快排的思想，找到第k大的分界点。左边的元素都是比它小的  
2）维护一个长度为k的容器，里面存放当前最小的k个数，遍历一个新的元素判断是否将其插入该容器。

# 3.代码 #

快排的思想，复杂度O(n)

void LeastK(int* array, int n,int k) {
        if (array == NULL || k <= 0 || k >= n)
            return;
        int left = 0;
        int right = n - 1;
        int pivot = mypartition(array, 0, n - 1);
        while (pivot != k - 1) {
            if (pivot > k - 1) {
                right = pivot - 1;
                pivot = mypartition(array, left, right);
            }
            else {
                left = pivot + 1;
                pivot = mypartition(array, left, right);
            }       
        }
        for (int i = 0; i < k; i++)
            cout << array[i] << " ";
        cout << endl;
    }

使用最大堆,复杂度nlog(k)

void LeastK(int* array, int n, int k) {
        if (array == NULL || k <= 0 || k >= n)
            return;
        priority_queue<int, vector<int>> maxHeap;//默认就是最大堆
        for (int i = 0; i < n; i++) {
            if (maxHeap.size() < k)
                maxHeap.push(array[i]);
            else if (array[i] < maxHeap.top()) {
                maxHeap.pop();
                maxHeap.push(array[i]);
            }
        }
        while (!maxHeap.empty())
        {
            cout << maxHeap.top() << " ";
            maxHeap.pop();
        }
        cout << endl;
    }

或者可以用multiset，降序排列，取set第一个元素是最大的。

#include<functional>
    multiset<int, greater<int>> myset;

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer - 最小的K个数

class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int

墨蓝/ 2022年09月25日 01:28/ 0 赞/ 88 阅读

相关剑指Offer 最小的K个数

题目描述: 输入n个整数，找出其中最小的k个数思路: 首先想到的是对数组进行按从小到大排序然后再选出最小的前K个数。排序算法里选择排序是每次排序都可以确定数组在最后排好

骑猪看日落/ 2022年06月10日 12:14/ 0 赞/ 211 阅读

相关剑指offer 最小的k个数

1.题目描述输入n个数字，找出其中最小的k个数。注：有的还会要求保持原有的顺序输出 2.分析两种思路： 1）利用快排的思想，找到第k大的分界点。左边的

男娘i/ 2022年06月08日 09:38/ 0 赞/ 174 阅读

相关剑指Offer:最小的k个数

题目：输入N个整数，找出其中最小的k个数。例如，输入4,5,1,6,2,7,3,8. 最小的4个数字是1,2,3,4. 思路：就是把那个容器只能存k个数，当容器未满时，直

骑猪看日落/ 2022年04月25日 03:08/ 0 赞/ 194 阅读

相关【剑指offer】最小的k个数

最小的k个数题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。解题思路

「爱情、让人受尽委屈。」/ 2022年04月10日 12:39/ 0 赞/ 206 阅读

相关剑指offer:最小的k个数

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 AC C++ Solution:

以你之姓@/ 2022年04月10日 08:58/ 0 赞/ 224 阅读

相关剑指offer:最小的k个数

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。思路：使用C++中的mutis

电玩女神/ 2022年02月26日 19:48/ 0 赞/ 205 阅读

相关剑指Offer-最小的K个数

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。解题思路—快排：时间复杂度O(nl

Dear 丶/ 2022年02月21日 16:54/ 0 赞/ 252 阅读

相关 [剑指offer]最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。最大堆时间复杂度O（nlogk）

ゞ浴缸里的玫瑰/ 2021年12月19日 22:29/ 0 赞/ 257 阅读

相关剑指offer：最小的K个数

试题：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。代码：使用有序结构存储这k个数就可以

旧城等待，/ 2021年06月24日 16:09/ 0 赞/ 372 阅读