首页 > 代码库 > 寻找最小的k个数（大顶堆方法）
寻找最小的k个数（大顶堆方法）
题目描述：查找最小的k个元素，输入n个整数，输出其中最小的k个。
一般的排序方法，如快排，时间复杂度为O（n*logn+k）;
大顶堆方法，时间复杂度为O（k+（n-k）*logk）;
如果建立k个元素的最小堆的话，那么其空间复杂度势为O（N），而建立k个元素的最大堆的空间复杂度为O（k）;
当面对海量数据处理的时候，大顶堆的方法是较为靠谱的，并且可以在面试时短时间内完成代码。
1 class Solution { 2 public: 3 void Swap(int &a,int &b) 4 { 5 a^=b; 6 b^=a; 7 a^=b; 8 } 9 10 void HeapAdjust(vector<int> &input,int i,int k)11 {12 int max = i;13 int leftchild = 2*i;14 int rightchild = 2*i+1;15 16 if(i<=k/2)17 {18 if(input[leftchild] > input[max] && leftchild <= k)19 {20 max = leftchild;21 }22 if(input[rightchild] > input[max] && rightchild <= k)23 {24 max = rightchild;25 }26 if(max!=i)27 {28 Swap(input[i],input[max]);29 HeapAdjust(input,max,k);30 }31 }32 }33 34 void BuildHeap(vector<int> &input,int k)35 {36 for(int i = k/2;i >0;i--)37 {38 HeapAdjust(input,i,k);39 }40 }41 42 vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {43 vector<int> result;44 vector<int> temp;45 int len = input.size();46 if(k>len)47 return result;48 49 temp.push_back(0);50 for(int i = 0;i < len;i++)51 {52 temp.push_back(input[i]);53 }54 55 BuildHeap(temp,k);56 57 for(int i = k+1;i <= len;i++)58 {59 if(temp[i] < temp[1])60 {61 temp[1] = temp[i];62 HeapAdjust(temp,1,k);63 }64 }65 66 for(int i = 0;i < k;i++)67 {68 result.push_back(temp[i+1]);69 }70 return result;71 }72 };
PS：类似快速排序的partition过程，时间复杂度可以做到O（N）。
寻找最小的k个数（大顶堆方法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。