https://pintia.cn/problem-sets/1102099479966621696/problems/1102099508777295878
本题目要求读入n个整数，要求用最少的比较次数，输出它们的最大值、第2大的值和第3大的值。例如，对于13 13 1 10 34 10这6个数，最大值为34，第2大的值为13，第3大的值为10。
输入格式:
输入有两行。第一行为整数个数n（≤1 000 000），第二行给出n个以空格分隔的整数。
输出格式:
对每一组输入，在一行中输出最大值、第2大的值和第3大的值值，中间以一个空格分隔，但行尾没有多余空格。 如果输入数据不足三个，则输出“Invalid Input”。 如果没有第3大的值，则输出“There is no third largest element”。 如果没有第2大和第3大的值，则输出“There is no second largest and third largest element”。
输入样例:
6
13 13 1 10 34 10
输出样例:
34 13 10
提交了几次才过 这是一种方法 只用数组 下面还有个用set 的 原理都一样
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
int arr[3];
const int inf = -200000000;
int main()
{
int N;
scanf("%d", &N);
arr[0] = inf;
arr[1] = inf;
arr[2] = inf;
for (int i = 0; i < N; i++) {
int a;
scanf("%d", &a);
int pos = 0, cnt = 0;
int temp = -inf;
for (int j = 0; j < 3; j++) {//找到最小的
if (arr[j] < temp) {
temp = arr[j];
pos = j;
}
}
for (int j = 0; j < 3; j++) {
if (a == arr[j]) cnt++;
}
if (arr[pos] < a && cnt == 0) {
arr[pos] = a;
}
}
if (N < 3) {
printf("Invalid Input\n");
return 0;
}
int cnt = 0;
for (int j = 0; j < 3; j++) {
if (arr[j] == inf) cnt++;
}
if (cnt == 2) {
printf("There is no second largest and third largest element\n");
return 0;
}
if (cnt == 1) {
printf("There is no third largest element\n");
return 0;
}
sort(arr, arr + 3);
for (int j = 0; j < 3; j++) {
printf("%d%c", arr[2 - j], j == 2 ? '\n':' ');
}
return 0;
}
用set 写起来快乐一些
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
set <int> st;
int main() {
int N;
scanf("%d", &N);
for (int i = 0, a; i < N; i++) {
scanf("%d", &a);
if (st.find(a) != st.end()) continue;
if (st.size() < 3) {
st.insert(a);
continue;
}
set <int>::iterator it = st.begin();
if (*it < a) {
st.insert(a);
st.erase(*it);
}
}
if (N < 3) {
printf("Invalid Input\n");
return 0;
}
int cnt = st.size();
if (cnt == 1) {
printf("There is no second largest and third largest element\n");
}
else if (cnt == 2) {
printf("There is no third largest element\n");
}
else {
set <int>::iterator it = st.begin();
int a, b, c;
a = *it; it++;
b = *it; it++;
c = *it; it++;
printf("%d %d %d\n", c, b, a);
}
return 0;
}
网友评论