HDU 1425 sort 题解

选择出数列中前k个最大的数。

这里由于数据特殊。所以能够使用hash表的方法：

#include <cstdio>

#include <algorithm>

#include <stdlib.h>

#include <limits>

using namespace std;

const int SIZE = 1000005;

const int SMALL = -500000;

bool arr[SIZE];

int main()

{

	int n, m, a, maxN = INT_MIN;

	while (~scanf("%d %d", &n, &m))

	{

		for (int i = 0; i < n; i++)

		{

			scanf("%d", &a);

			arr[a - SMALL] = true;

			if (a - SMALL > maxN) maxN = a - SMALL;

		}

		for (int i = maxN; i >= 0 && m; i--)

		{

			if (arr[i])

			{

				if (m > 1) printf("%d ", i + SMALL);

				else printf("%d\n", i + SMALL);

				m--;

			}

		}

	}

	return 0;

}

也能够使用选择前k个数，然后排序，只是难度高非常多：

#include <cstdio>

#include <algorithm>

#include <stdlib.h>

#include <time.h>

using namespace std;

int partition(int *arr, int low, int up)

{

	for (int i = low; i < up; i++)

		if (arr[i] >= arr[up]) swap(arr[low++], arr[i]);

	swap(arr[low], arr[up]);

	return low;

}

//K作为绝对下标位置处理

void randSelectK(int *arr, int low, int up, int K)

{

	int r = low + rand() % (up - low + 1);

	swap(arr[r], arr[up]);

	int idx = partition(arr, low, up);

	if (idx > K) randSelectK(arr, low, idx-1, K);

	else if (idx < K) randSelectK(arr, idx+1, up, K);

}

void randQuickSort(int *arr, int low, int up)

{

	if (low >= up) return ;//不能是low == up

	int r = low + rand() % (up - low + 1);

	swap(arr[r], arr[up]);

	int mid = partition(arr, low, up);

	randQuickSort(arr, low, mid-1);

	randQuickSort(arr, mid+1, up);

}

const int SIZE = 1000000;

int arr[SIZE];

int main()

{

	int n, m;

	srand(unsigned(time(NULL)));

	while(~scanf("%d %d", &n, &m))

	{

		for (int i = 0; i < n; i++)

			scanf("%d", &arr[i]);

		randSelectK(arr, 0, n-1, m-1);

		randQuickSort(arr, 0, m-1);

		for (int i = 0; i < m-1; i++)

		{

			printf("%d ", arr[i]);

		}

		printf("%d\n", arr[m-1]);

	}

	return 0;

}