题目描述：
给你n个整数，请按从大到小的顺序输出其中前m大的数。
输入：
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
输出：
对每组测试数据按从大到小的顺序输出前m大的数。
样例输入：
5 33 -35 92 213 -644
样例输出：
213 92 3
解法1
解法一
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1000000
using namespace std;
int a[N];
int main()
{
int n, m, i, flag = 0;
while (scanf_s("%d%d", &n, &m) != EOF) {
for (i = 0;i<n;i++)
scanf_s("%d", &a[i]);
sort(a, a + n);
flag = n - 1;
printf("%d", a[flag]);
flag -= 1;
for (i = m;i>1;i--) {
printf(" %d", a[flag]);
flag--;
}
cout << endl;
}
return 0;
}
解法2
解法二
#include <stdio.h>
#define OFFSET 500000 //偏移量,用于补偿实际数字与数组下标之间偏移
int Hash[1000001]; //偏移量,用于补偿实际数字与数组下标之间偏移
int main() {
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = -500000;i <= 500000;i++) {
Hash[i + OFFSET] = 0;
}//初始化,将每个数字都标记为未出现
for (int i = 1;i <= n;i++) {
int x;
scanf("%d", &x);
Hash[x + OFFSET] = 1; //凡是出现过的数字,该数组元素均被设置成1
}
for (int i = 500000;i >= -500000;i--) { //输出前m个数
if (Hash[i + OFFSET] == 1) { //若该数字在输入中出现
printf("%d", i); //输出该数字
m--; //输出一个数字后,m减一,直至m变为0
if (m != 0) printf(" "); //注意格式,若m个数未被输出完毕,在输出的 数字后紧跟一个空格
else {
printf("\n"); //若m个数字已经被输出完毕,则在输出的数字后面紧跟 一个换行, 并跳出遍历循环
break;
}
}
}
}
return 0;
}
解法3
解法三
#include<stdio.h>
#define N 1000000
int array[N];
void quick_sort(int s[], int l, int r)
{
int i, j, x;
if (l < r)
{
i = l;
j = r;
x = s[i];
while (i < j)
{
while (i < j && s[j] > x)
j--; /* 从右向左找第一个小于x的数 */
if (i < j)
s[i++] = s[j];
while (i < j && s[i] < x)
i++; /* 从左向右找第一个大于x的数 */
if (i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); /* 递归调用 */
quick_sort(s, i + 1, r);
}
}
int main() {
int n, m;
while (scanf_s("%d%d", &n, &m) != EOF) {
for (int i = 0;i < n;i++) {
scanf_s("%d", &array[i]);
}
quick_sort(array, 0, n - 1);
int temp = m;
for (int j = n - 1;j >= n-temp;j--) {
printf_s("%d", array[j]);
m--;
if (m != 0)
printf(" ");
else {
printf("\n");
break;
}
}
}
return 0;
}
总结：解法三是我自己写的，一次快速排序+反向的for循环。
过程中遇到的错误
输出格式不正确。
解决办法：每次输出数字后m-1，m等于0的时候跳出循环即可。
