[编程之美_2-5]寻找最大的k个数

这个问题与寻找第k大/小数等价。
方法1: 直接排序输出[编程之美书上说：不同的排序方法时间复杂度不一样，诚然，因为不需要n个数有序，只需要最大的k个数即可]
选用快速排序：

1
2
3
4
5
6


vector<int> FindMostKSort(vector<int>& vNumbers, int k)
{
   sort(vNumbers.begin(),vNumbers.end());
   vector<int> vKNumbers(vNumbers.rbegin(), vNumbers.rbegin() + k);
   return vKNumbers;
}

方法2: 实际上并不需要全部数有序，其实可以模拟快速排序的划分过程，求某个数排序之后在第k个位置即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


void swap(int &a, int &b)
{
   int tmp = a;
   a = b;
   b = tmp;
}
void FindMostKPartition(vector<int>& vNumber, int k, int left, int right)
{
   int index = left;
   int tmp = vNumber[index];
   int i = left;
   int j = right;
   while (i < j)
   {
       while(i < j && vNumber[j] >= vNumber[index]) j--;
       swap(vNumber[j], vNumber[index]);
       index = j;
       while(i < j && vNumber[i] <= vNumber[index]) i++;
       swap(vNumber[i], vNumber[index]);
       index = i;
   }
   if (index - left + 1 == k)
   {
       cout << vNumber[index] << endl;
   }
   else if (index - left + 1 < k)
   {
       FindMostKPartition(vNumber, k - (index - left + 1), index + 1, right);
   }
   else
   {
       FindMostKPartition(vNumber, k, left, index - 1);
   }
}

方法3: 堆排序[维护一个k数量的最小堆即可，STL代码如此短啊，不过可以自己用数组实现堆]

PS: 排序均用STL实现，具体的排序自己实现，将在近期尝试编写。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void FindMostKHeap(vector<int>& vNumbers, int k)
{
   vector<int> vKNumbers(vNumbers.begin(), vNumbers.begin() + k);
   make_heap(vKNumbers.begin(), vKNumbers.end(), greater<int>());
   for (vector<int>::size_type i = k; i < vNumbers.size(); i++)
   {
       if (vNumbers[i] > vKNumbers[0])
       {
           vKNumbers[0] = vNumbers[i];
           make_heap(vKNumbers.begin(), vKNumbers.end(), greater<int>());
       }
   }
   cout << vKNumbers[0] << endl;
}