最小的k个数

  1 // 最小的k个数.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include <iostream>
  6 #include <set>
  7 #include <vector>
  8 #include <queue>
  9 using namespace std;
 10 
 11 //  set中默认是从大到小的顺序，即最先取出的是最小值
 12 //  此处为从小到大，最先取出的是最大值
 13 typedef multiset<int,greater<int>> inSet;
 14 typedef multiset<int,greater<int>>::iterator setIterator;
 15 
 16 //  基于红黑树
 17 void GetNumber(vector<int> &data,inSet &leastNumber,int k) 
 18 {
 19     if(k<=0 || data.size()==0)
 20         return ;
 21     leastNumber.clear();
 22     vector<int>::iterator it = data.begin();
 23     for(;it!=data.end();++it)
 24     {
 25         if(leastNumber.size()<k)
 26             leastNumber.insert(*it);
 27         else{
 28             setIterator s = leastNumber.begin();
 29 
 30             if(*it < *s)
 31             {
 32                 leastNumber.erase(s);
 33                 leastNumber.insert(*it);
 34             }
 35         }
 36     }
 37     setIterator s = least.begin();
 38     for(;s!=least.end();++s)
 39         cout<<*s<<" ";
 40     cout<<endl;
 41 }
 42 
 43 //  基于优先队列
 44 void GetNumber2(vector<int> &data,int k)
 45 {
 46     if(data.size()==0 || k<1)
 47         return ;
 48     //  top取出的是最小值，即是按从大到小排列的
 49     //priority_queue<int,vector<int>,greater<int>> q;
 50     // 默认是从小到大排列，即最先取出的是最大值
 51     priority_queue<int> q;
 52     vector<int>::iterator it = data.begin();
 53     for(;it!=data.end();++it)
 54     {
 55         if(q.size()<k)
 56             q.push(*it);
 57         else{
 58             if(*it < q.top())
 59             {
 60                 q.pop();
 61                 q.push((*it));
 62             }
 63         }
 64     }
 65     while(q.size()>0)
 66     {
 67         cout<<q.top()<<" ";
 68         q.pop();
 69     }
 70     cout<<endl;
 71 }
 72 
 73 int Partition(int *a,int start,int end)
 74 {
 75     if(start < end)
 76     {
 77         int i=start,j=end;
 78         int x = a[start];
 79         while(i<j)
 80         {
 81             while(i<j && a[j]>x)
 82                 j--;
 83             if(i<j)
 84                 a[i++] = a[j];
 85             while(i<j && a[i]<x)
 86                 i++;
 87             if(i<j)
 88                 a[j--] = a[i];
 89         }
 90         a[i] = x;
 91         return i;
 92     }
 93 }
 94 
 95 //  基于分治思想，但会修改数组，时间复杂度为O(N)
 96 void GetNumber2(int *a,int len,int k)
 97 {
 98     if(a==NULL || len<=0 || k<=0)
 99         return ;
100     int start = 0,end = len-1;
101     int index = Partition(a,start,end);
102         //取出最小的K个数
103     while(index != k-1)
104     {
105         if(index < k-1)
106         {
107             start = index +1;
108             index = Partition(a,start,end);
109         }else{
110             end = index -1;
111             index = Partition(a,start,end);
112         }
113     }
114     for(int i=0;i<k;++i)
115         cout<<a[i]<<" ";
116     cout<<endl;
117 }
118 
119 
120 int _tmain(int argc, _TCHAR* argv[])
121 {
122     vector<int> v;
123     v.push_back(1);
124     v.push_back(3);
125     v.push_back(9);
126     v.push_back(2);
127     v.push_back(3);
128     v.push_back(8);
129     v.push_back(6);
130     inSet least;
131     GetNumber1(v,least,5);
132 
133     GetNumber2(v,5);
134 
135     int a[]={3,1,35,65,7,3,8,2};
136     GetNumber2(a,8,1);
137 
138     system("pause");
139     return 0;
140 }
141