資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告