数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的第三大数
假设我们有一个非空的整数数组；我们必须找到该数组中的第三大数。如果没有第三大数，则返回最大数。挑战在于，我们必须使用线性时间复杂度来解决此问题。
因此，如果输入类似于 [5,3,8,9,1,4,6,2]，则输出将为 6。
为了解决这个问题，我们将遵循以下步骤：
用 NULL 初始化 a、b、c
对于初始化 i := 0，当 i < nums 的大小，更新（i 增加 1），执行：
如果 a 为 null 或 nums[i] >= a 的值，则：
如果 a 不为 null 且 nums[i] > a 的值，则：
c := b，b := a
a := nums[i]
否则，当 b 为 null 或 nums[i] >= b 的值，则：
如果 b 不为 null 且 nums[i] > b 的值，则：
c := b
b := nums[i]
否则，当 c 为 null 或 nums[i] >= c 的值，则：
c := nums[i]
返回（如果 c 为 null，则 a 的值，否则 c 的值）
示例
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int thirdMax(vector<int>& nums) {
int *a, *b, *c;
a = b = c = NULL;
for (int i = 0; i < nums.size(); ++i) {
if (!a || nums[i] >= *a) {
if (a && nums[i] > *a) {
c = b;
b = a;
}
a = &nums[i];
}
else if (!b || nums[i] >= *b) {
if (b && nums[i] > *b) {
c = b;
}
b = &nums[i];
}
else if (!c || nums[i] >= *c) {
c = &nums[i];
}
}
return !c ? *a : *c;
}
};
main(){
Solution ob;
vector<int> v = {5,3,8,9,1,4,6,2};
cout << (ob.thirdMax(v));
}输入
{5,3,8,9,1,4,6,2}输出
6
更新于： 2020-06-10
354 次浏览
广告