小张须要从一批数量庞大的正整数中挑选出第k小的数。由于数据量太庞大，挑选起来非常费劲，希望你能编程帮他进行挑选。
输入 第一行第一个是数据的个数n(10<=n<=10 6)。第二个是须要挑选出的数据的序号k(1<=k<=10 5)，n和k以空格分隔； 第二行以后是n个数据T(1<=T<=10 9)，数据之间以空格或者换行符分隔。 输出 第k小数（假设有同样大小的也进行排序。比如对1,2,3,8,8。第4小的为8。第5小的也为8）。 例子输入 10 5 1 3 8 20 2 9 10 12 8 9 例子输出 8 解题方案 借用于高速排序思想，查找第K小元素 代码 #include <iostream> #include <fstream> using namespace std; void main_solution(); void read_data( int *& data,int &n,int &k ); int min_k(int *data,int s,int e,int k); int main() { main_solution(); system("pause"); return 0; } void read_data( int *& data,int &n,int &k ) { ifstream reader; reader.open( "data.txt" ); reader>>n; reader>>k; data = new int[n]; for(int i=0;i<n;i++) { reader>>data[i]; } reader.close(); } int min_k(int *data,int s,int e,int k) { int t = s; int another = e; while(t != another) { if( t < another ) { if( data[t] <= data[another] ) another --; else { int d = data[another]; data[another] = data[t]; data[t] = d; d = another; another = t; t = d; } } else { if( data[t] >= data[another] ) another ++; else { int d = data[another]; data[another] = data[t]; data[t] = d; d = another; another = t; t = d; } } } if( k == t-s+1 ) return data[t]; else if( k < t-s+1 ) return min_k(data,s,t-1,k); else return min_k(data,t+1,e,k - (t-s+1)); } void main_solution() { int * data; int n; int k; read_data(data,n,k); cout<<min_k(data,0,n-1,k)<<endl; }转载于:https://www.cnblogs.com/bhlsheji/p/4593854.html
