C语言/数据结构数组题解：寻找数组中第三大的不同数字——O(n)时间O(1)空间
问题描述
小明正在参加一个在线游戏比赛，比赛结束后系统会显示所有玩家的分数列表。由于系统只显示前三名的分数，小明想知道自己是否进入了前三名。但是系统只显示了所有玩家的分数，没有直接给出排名。现在需要你帮助小明快速找出分数列表中第三大的分数是多少。
要求：
- 设计一个算法，找出给定分数列表中第三大的分数。
- 如果列表中不同分数的数量少于三个，则返回最大的分数。
- 注意分数可能重复，排名时重复的分数只算一个名次。
测试样例
样例1：
输入：
scores = [5, 2, 8, 8, 3, 5, 1]输出：3解释：去重排序后分数为 [1, 2, 3, 5, 8]，第三大的分数是 3。
样例2：
输入：
scores = [10, 10, 10]输出：10解释：只有一种分数，第三大的分数就是最大的分数 10。
样例3：
输入：
scores = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]输出：8解释：去重后分数从大到小为 [10, 9, 8, ...]，第三大的分数是 8。
约束条件
- 1 ≤ scores.length ≤ 1000
- -1000 ≤ scores[i] ≤ 1000
- 分数列表可能包含重复值
- 如果不同分数的数量少于三个，则返回最大的分数
程序代码
#include <stdio.h>
#include <limits.h>
int thirdMax(int* scores, int scoresSize) {
long first = -1000000000;
long second = -1000000000;
long third = -1000000000;
for (int i = 0; i < scoresSize; i++) {
int x = scores[i];
// 跳过重复值
if (x == first || x == second || x == third) {
continue;
}
if (x > first) {
third = second;
second = first;
first = x;
} else if (x > second) {
third = second;
second = x;
} else if (x > third) {
third = x;
}
}
// 如果不同分数少于3个，返回最大值
if (third == -1000000000) {
return first;
}
return third;
}
int main() {
int scores1[] = {5, 2, 8, 8, 3, 5, 1};
int scores2[] = {10, 10, 10};
int scores3[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
printf("%d\n", thirdMax(scores1, 7)); // 3
printf("%d\n", thirdMax(scores2, 3)); // 10
printf("%d\n", thirdMax(scores3, 10)); // 8
return 0;
}
#include <stdio.h> #include <limits.h> int thirdMax(int* scores, int scoresSize) { long first = -1000000000; long second = -1000000000; long third = -1000000000; for (int i = 0; i < scoresSize; i++) { int x = scores[i]; // 跳过重复值 if (x == first || x == second || x == third) { continue; } if (x > first) { third = second; second = first; first = x; } else if (x > second) { third = second; second = x; } else if (x > third) { third = x; } } // 如果不同分数少于3个，返回最大值 if (third == -1000000000) { return first; } return third; } int main() { int scores1[] = {5, 2, 8, 8, 3, 5, 1}; int scores2[] = {10, 10, 10}; int scores3[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; printf("%d\n", thirdMax(scores1, 7)); // 3 printf("%d\n", thirdMax(scores2, 3)); // 10 printf("%d\n", thirdMax(scores3, 10)); // 8 return 0; }