Third Maximum Number trong C++

Tìm số lớn nhất thứ 3 trong mảng (phân biệt giá trị). Nếu không có, trả về số lớn nhất. Yêu cầu O(n).

Ví dụ: [5,3,8,9,1,4,6,2] → các giá trị phân biệt: 9,8,6,5,4,3,2,1 → lớn nhất thứ 3 là 6.

Giải thuật O(n)

Duy trì 3 biến a, b, c (lớn nhất, lớn nhì, lớn ba) kiểu con trỏ hoặc optional.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long long a = LLONG_MIN, b = LLONG_MIN, c = LLONG_MIN;
        for (int x : nums) {
            if (x == a || x == b || x == c) continue;
            if (x > a) { c = b; b = a; a = x; }
            else if (x > b) { c = b; b = x; }
            else if (x > c) { c = x; }
        }
        return (c == LLONG_MIN) ? a : c;
    }
};

int main() {
    Solution ob;
    vector<int> v = {5,3,8,9,1,4,6,2};
    cout << ob.thirdMax(v); // 6
    return 0;
}

Đầu vào / Đầu ra

Input: {5,3,8,9,1,4,6,2}
Output: 6