寻找前K大数

寻找前K大数，虽然这个问题已经被做烂了，但是无意中看到之前A题时候的一个代码，还是忍不住改了改想提高下效率，从O(NlogN)降到O（KlogN）。

3 1
2 5 -1
5 3
1 2 3 4 5
0 0

5
5 4 3

当时用的是很简单的冒泡和sort，恩，也就是对数组全部元素排序，复杂度O(NlogN), 但是当K很小时，比如题目中K<=10的情况无疑浪费了。因此用quicksort的思路，每次将数组partition成两部分，一边＜key，一边＞key。然后迭代地找前k大数。

code：

//
//  k_biggest_num.c
//  ACM
//  Find the k biggest number in an array
//
//  Created by Rachel on 14-2-13.
//  Copyright (c) 2014年 ZJU. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <functional>
#include <utility>
using namespace std;
#define N 100010
#define K 11
typedef int DT;//datatype: DT
DT A[N];
DT kbig[K];
DT partition_r[N],partition_l[N];

void swap(DT* a, DT* b)
{
    DT t = *a;
    *a = *b;
    *b = t;
}

pair<int,int> findKbig(int left, int right, int k)
{
    int l = left, r = right, m = (l+r)/2;
	DT key = A[m];
	while(l<=r)
	{
		while(A[l]<key) l++;
		while(A[r]>key) r--;
		if(l<=r) 
		{
			swap(&A[l],&A[r]); l++; r--;
		}
	}
	/*
	for(int i = left; i<=right; i++)
		cout<<A[i]<<" ";
	cout<<endl;
	*/

	int n = right-l+1; //#elements > key
	pair<int, int> lr = make_pair(l,right);
	if(right-left+1==k)
	{
		lr.first = left;
		return lr;
	}
	else if(n==k)
		return lr;
	else if(n>k)
		return findKbig(l,right,k);
	else
	{
		lr.first = findKbig(left,l-1,k-n).first;
		return lr;
	}
}

int main()
{
    int i,n,k;
    while (true) {
        cin>>n>>k;
        
        if (n==0 && k==0) {
            break;
        }
        k = k>n?n:k;
        for (i=0; i<n; i++) {
            cin>>A[i];
        }
        pair<int,int> P = findKbig(0,n-1,k);
		int l = P.first, r = P.second;
		DT res[K];
		memset(res,0,sizeof(res));
		for(i = l; i<=r ; i++)
			res[i-l] = A[i];
        sort(res, res+K,greater<int>());
        for (i = 0; i<k-1; i++) {
            cout<<res[i]<<" ";
        }
        cout<<res[i]<<endl;
    }
    return 0;
}

6 3

2 4 6 9 1 2

10 3

2 3 4 1 53 23 52 32 32 32

4 2

24 34 24 24

5 6

1 2 3 4 5

5 3 

5 3 1 4 2

5 3

1 2 1 1 1

5 3

1 2 3 4 5

10 4

2 5 3 6 2 7 8 7 4 3

关于Algorithms更多的学习资料将继续更新，敬请关注本博客和新浪微博Rachel Zhang。

寻找前K大数

原文：http://blog.csdn.net/abcjennifer/article/details/19245945