速い列の思想を使ってn番目の大きい値を求めます
1305 ワード
#include "iostream"
#include "vector"
#include <ctime>
#include <cstdlib>
using namespace std;
template <typename T>
int partition(vector<T> &a,int low,int high){
T temp = a[low];
while(low < high){
while((low < high) && (a[high] > temp)) --high;
if(low < high) a[low++] = a[high];
while((low < high) && a[low] < temp) ++low;
if(low < high) a[high--] = a[low];
}
a[low] = temp;
return low;
}
template <typename T>
T nthElement(vector<T> &a,int low,int high,int n){
if(low > high || n < 1 || n > high - low + 1) {
cout<<"error"<<endl;
system("pause");
}
int pos;
while(true){
pos = partition(a,low,high);
if(low + n - 1 == pos) return a[pos];
else if(low + n -1 < pos) high = pos - 1;
else {
n = n - (pos - low + 1);// pos pos - low + 1 n
low = pos + 1;
}
}
}
int main(int argc, char const *argv[])
{
int num = 6;
srand(time(0));
std::vector<int> a(num);
for (int i = 0; i < num; ++i)
{
//seed
int rand_num = rand()%100;
a[i] = rand_num;
cout<<rand_num<<"\t";
}
cout<<endl;
cout<<nthElement(a,0,num - 1,3)<<endl;
}