第k大的数

在许多题目中都会出现寻找第k大的数的类似问题，最简单的做法就是先排序在找位置就可以找到第k大的数，但是排序的做法显然不能满足我们的要求，排序的时间复杂度是O(nlogn)，不够快，我们一般可以用快速排序的思想，用O(n)的时间内就可以找到第k大的数，这里我们只讲解C++ STL的函数nth_element。

先看一下STL

template<class _RanIt, class _Pr> inline
    void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
 
template<class _RanIt> inline
	void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last)

从STL中可以看出nth_element可以带3个或者4个参数，第一个就是寻找的数组或者容器开始的位置，第二个就是寻找的第k大的数，第三个就是寻找的数字或者容器结束的位置。

如果用于数组：

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
    int a[10] = { 8, 9, 1, 2, 4, 3, 5, 6, 7, 10 };
    nth_element(a, a + 5, a + 10, std::greater<int>());
    cout << "数组中的中间元素是" << a[5] << endl;
    nth_element(a, a, a + 10, std::greater<int>());
    cout << "数组中第1大元素为" << a[0] << endl;
    nth_element(a, a + 1, a + 10, std::greater<int>());
    cout << "数组中第2大元素是" << a[1] << endl;
}

如果用于容器vector：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int main()
{
	vector<int> v;
	int n,a;
	cin>>n;
	for(int i=0;i<n;i++)	cin>>a,v.pb(a);
	for(int i=0;i<n;i++)	cout<<v[i]<<' ';
	cout<<endl;
	vector<int>::iterator it;
	for(it=v.begin();it<v.end();it++)	cout<<*it<<' ';
	cout<<endl;
	nth_element(v.begin(),v.begin(),v.end());
	for(it=v.begin();it<v.end();it++)	cout<<*it<<' ';
	return 0;
}

如果加上第4个参数，那么就是要进行自定义查找了，自定义的查找方式。

比如对结构体进行自定义的方式的查找

struct node
{
	int ct,id;
}t[N*10];
int cmp(node a,node b)
{
	if(a.ct==b.ct)	return a.id<b.id;
	else	return a.ct<b.ct;
}

nth_element(t+1,t+k,t+n+1,cmp);