寻找第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
void quickSort(int* num, int left,int right)
{
	if(left>=right)
	{
		return;
	}
	int key=num[left];
	int first=left;
	int last=right;
	while(first<last)
	{
		while(first<last&&num[last]>=key)//右边的先往左进行，为了第一个小于Key的数放到
		num[left]的位置
		{
			last--;
		}
		num[first]=num[last]; //第一次把key值所在的位置占据
		while(first<last&&num[first]<=key)
		{
			first++;
		}
		num[last]=num[first];
	}
	num[first]=key;  //被替换掉的key，在最后占据first=last的位置，此时左边小于Key，右边大于key
	quickSort(num,left,first-1);
	quickSort(num,first+1,right);
}

描述：寻找数组中第K大的数字

得到了前k大的数，显然顺便得到第k大的数，即：该问题至少存在O(Nlogk)的算法。
Partition()函数返回key值的下标

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<stdio.h>

int Partition(int* num, int left,int right)
{
	if(left>=right)
	{
		return -1;
	}
	int key=num[left];
	int first=left;
	int last=right;
	while(first<last)
	{
		while(first<last&&num[last]>=key)//右边的先往左进行，为了第一个小于Key的数放到num[left]的位置
		{
			last--;
		}
		num[first]=num[last]; //第一次把key值所在的位置占据
		while(first<last&&num[first]<=key)
		{
			first++;
		}
		num[last]=num[first];
	}
	num[first]=key;  //被替换掉的key，在最后占据first=last的位置，此时左边小于Key，右边大于key
	return first;
}

int main()
{
	int num[100];
	int count=0;
	while(scanf("%d",&num[count++])!=EOF)
	{
		if(getchar()=='\n')
			break;
	}
	int k;
	while(scanf("%d",&k)!=EOF)
    {
	int tar=count-k;
	int m=Partition(num,0,count-1);
	while(m!=tar)
	{
		if(m<tar)
		{
			m=Partition(num,m+1,count-1);
		}
		else
		{
			m=Partition(num,0,m-1);
		}
	}
	printf("%d\n",num[m]);
    }
	return 0;
}