寻找第k大数
发布时间:2020-12-14 02:48:33 所属栏目:大数据 来源:网络整理
导读:/************************************************************************* File Name: k_fenshu.cpp Author: wangzhicheng Mail: 2363702560@qq.com Created Time: Sun 18 Jan 2015 10:47:12 PM WSTThis is a free program,you can modify or redistrib
/************************************************************************* > File Name: k_fenshu.cpp > Author: wangzhicheng > Mail: 2363702560@qq.com > Created Time: Sun 18 Jan 2015 10:47:12 PM WST This is a free program,you can modify or redistribute it under the term of GNU ************************************************************************/ // search the k_th max number // for example,3,1,2,the 1 max number is 3,the 2 max number is 2 #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <time.h> #include <iostream> #include <vector> #include <algorithm> using namespace std; /* * @purpose:partition a array,this is generally included in quick sort * */ int partition(vector<int>&v,int start,int end) { int i,j; int k; int tmp; i = start; j = end; tmp = v[i]; while(i < j) { while(i < j && v[j] > tmp) j--; if(i < j) v[i++] = v[j]; while(i < j && v[i] < tmp) i++; if(i < j) v[j--] = v[i]; } v[i] = tmp; return i; } void find_k_max(vector<int>&v,int end,int k_th,int &k_max) { int pivot; int k; if(start <= end) { pivot = partition(v,start,end); k = end - pivot + 1; if(k == k_th) k_max = v[k]; else if(k > k_th) find_k_max(v,pivot + 1,end,k_th,k_max); else find_k_max(v,pivot - 1,k_th - k,k_max); } } int main() { int n; int k_th,k_max; int i; cout << "number = "; cin >> n; cout << "k_th = "; cin >> k_th; if(k_th < 1 || k_th > n) { cerr << "imput error...!" << endl; exit(1); } vector<int>v(n); for(i = 0;i < n;i++) { cout << i << " = "; cin >> v[i]; } find_k_max(v,n - 1,k_max); cout << "k_max = " << k_max << endl; return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |