最小的K个数_牛客题霸_牛客网
描述
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：0≤k,n≤100000≤k,n≤10000，数组中每个数的大小0≤val≤10000≤val≤1000
要求：空间复杂度 O(n)O(n) ，时间复杂度 O(nlogk)O(nlogk)
示例1
输入：[4,5,1,6,2,7,3,8],4 返回值：[1,2,3,4]
说明：返回最小的4个数即可，返回[1,3,2,4]也可以
解法：
1.分治：快排思想，比较K和分治后pos的大小，如果相等，说明找到了，pos前面的数就是结果.,题目要求还需要对pos前的元素进行排序。
2.维护一个K个节点的大根堆，对于[k,n-1]之间的元素，每次拿堆顶元素和当前元素对比，交
换比堆顶元素小的，重新调整。
3.书中解题，多重哈希表，哈希表从大到小排序，依次往哈希表插入k个元素，如果哈希表有了k个元素，往后每遍历一个值，把0号元素(最大值)和当前元素进行对比，0号元素比进来的元素小，删除0号元素，插入当前元素。
1.分治
#include <any>
#include <functional>
#include <iterator>
#include <utility>
#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param input int整型vector * @param k int整型 * @return int整型vector*/// 分治int partition(vector<int>& input, int left, int right, int k ){int i = left, j = left;for(; i < right; ++i){if(input[i] < input[right]){swap(input[i], input[j]);++j;}}swap(input[j],input[right]);if(j == k - 1) return j;else if(j > k - 1) return partition(input, left, j-1, k);else if(j < k - 1) return partition(input, j+1, right, k);return -1;}vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {// write code hereif(!k || input.empty()) return vector<int>{};vector<int> res;// 1.分治int res_pos = partition(input, 0, input.size() - 1, k);copy_n(input.begin(), k,back_inserter(res));return res;}};2.K个节点的大根堆
#include <any>
#include <functional>
#include <iterator>
#include <utility>
#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param input int整型vector * @param k int整型 * @return int整型vector*/vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {// write code hereif(!k || input.empty()) return vector<int>{};vector<int> res;// 2.K个结点的大根堆int nums_size = input.size();for(int idx = k / 2 - 1; idx >=0 ; --idx){adjustMaxHeap(input, idx, k);} //维护K个结点的大根堆for(int idx = k; idx < nums_size; ++idx){if(input[0] > input[idx]){ //把K后面的值依次和堆顶比较, 如果堆顶元素>新插入的元素swap(input[0], input[idx]);adjustMaxHeap(input, 0, k); //调整为大根堆}}copy_n(input.begin(), k, back_inserter(res));sort(res.begin(), res.end()); return res;}//维护一个k个结点的大根堆void adjustMaxHeap(vector<int>&input, int pos, int len){int dad = pos;int son = 2*dad +1;while(son < len){if(son +1 < len && input[son] < input[son+1]){++son;}if(input[son] > input[dad] ){swap(input[son],input[dad]);dad = son;son = 2 * dad + 1;}else break;}}};3.multi_set
#include <any>
#include <functional>
#include <iterator>
#include <utility>
#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param input int整型vector * @param k int整型 * @return int整型vector*/vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {// write code hereif(!k || input.empty()) return vector<int>{};vector<int> res;//书中解题3，多重哈希表，哈希表从大到小排序，依次往哈希表插入k个元素，//如果哈希表有了k个元素，往后每遍历一个值，把0号元素和当前元素进行对比，0号元素比进来的元素小，删除0号元素，插入当前元素。multiset<int, greater<int>> hash_table;for(int idx = 0; idx < input.size(); ++idx){if(hash_table.size() < k){ hash_table.insert(input[idx]);}else{if(*hash_table.begin() > input[idx]){hash_table.erase(hash_table.begin());hash_table.insert(input[idx]);}}}// //从小到大插入结果容器vectorcopy(hash_table.rbegin(),hash_table.rend(), back_inserter(res));return res;}};
