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.hint 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)); // 3printf(%d\n, thirdMax(scores2, 3)); // 10printf(%d\n, thirdMax(scores3, 10)); // 8return 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; }运行结果