题目

二分找第K大数

提交数: 415, 通过率: 24.58%, 平均分: 34.8

题目描述:

数组a ( a[1]~a[n]，n≥1 ) 中的数据，为各不相同且无序的整数，为了在数组a中查找第k大(1≤k≤n)的整数，小李借鉴对分查找的思想，编写的C++程序段如下：

输入格式:

第一行，一个数n。

第二行，n个数，以一个逗号分隔每个数。

第三行，一个数中k。

输出格式:

一个表示第K大的数。

数据范围:

n<=100,000

a数组中的每个数小于10000

样例输入:

9
12,4,67,23,90,6,7,11,12
4

样例输出:

提示:

请完善下面的程序：

#include<bits/stdc++.h>
using namespace std;
int n, k, a[300005];
int low, high, cnt, m,x;
string s;
int main() {
	cin >>n;
	//a = 12,4,67,23,90,6,7,11,12
	cin >> s;
	s = s+',';
	for ( int i=0; i<s.length(); i++){
		if (s[i]!=',') _______(1)________;   //填空1
		else {
			a[++n] = x;
			x = 0;
		}
	}
	cin >> k;	
	low=a[1] ;
	high=a[n];
	for (int i=1; i<=n; i++) {
		if ( a[i] < low )  low = a[i];
		if ( a[i]> high  ) high = a[i];
	}
	while (low < high) {
		m=(low+high) / 2;
		cnt = 0;
		for (int i=1; i<=n; i++)
			if (a[i] > m ) cnt += 1;
		if (cnt >= k)
			_____(2)______ ;   //填空2
		else
			______(3)_____ ;   //填空3
	}
	cout << high;
}

时间限制: 1000ms
空间限制: 256MB

来源: 高中教材