博客

1.问题

数学语言：给无序序列集中有n个元素，查询次数m和一个整数k，1<=k<=n，找出这n个元素中第k大的元素。

2.解析

利用快速排序，可以从序列中取一个中点mid,然后把序列分成小于等于mid和大于等于mid的两部分，由两个部分的元素个数和k的大小关系可以确定这个数是在哪个部分，以此类推，进行递归查找。

3.设计

if (两边指针相交) 
		return -1;
	if (两边指针重合)
		return 当前元素;
	i = quicksort(a, l, r);//对当前序列进行快速排序
	j = i - l + 1;//当前元素在当前序列的位置大小
	if (j == k)
		返回当前值;
	else if (j > k)
		递归查找左边集合;
	else
		递归查找右边集合;

4.分析

最坏情况:

T(n)=T(n-1)+n-1

T(n)=O(n^2 )

平均值：

T(n)=T(n/2)+n-1

T(n)=O(n)

5.源码

#include<map>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn = 1e3 + 10;
#define ll long long
int i, j, k;
int n, m;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int a[maxn];
int quicksort(int a[], int l, int r) {
	if (l < r) {
		i = l, j = r;
		int value = a[i];
		while (i < j) {
			while (i < j && a[j] >= value)
				j--;
			if (i < j)
				a[i++] = a[j];
			while (i < j && a[i] < value)
				i++;
			if (i < j) a[j--] = a[i];
		}
		a[i] = value;
		return i;
	}
	return -1;
}

//main
int divide(int a[], int l, int r, int k) {
	if (l > r) 
		return -1;
	if (l == r)
		return a[l];
	i = quicksort(a, l, r);
	j = i - l + 1;
	if (j == k)
		return a[i];
	else if (j > k)
		return divide(a, l, i, k);
	else
		return divide(a, i + 1, r, k - j);
}

int main() {
	cin >> n >> m;//n 是元素个数,m是查询次数
	for (i = 1; i <= n; i++)
		cin >> a[i];
	while (m--) {
		cin >> k;//第k小数
		cout << divide(a, 1, n, k) << endl;
	}
	return 0;
}