Third Maximum Number ใน C++

แนวคิด

สมมติว่ามีอาร์เรย์จำนวนเต็มไม่ว่าง ให้หาตัวเลขสูงสุดอันดับสามในอาร์เรย์นี้ หากไม่มีตัวเลขอันดับสาม ให้คืนค่าตัวเลขสูงสุด แท้ท้าทายคือต้องแก้ด้วยเวลาเชิงเส้น

เช่น ถ้าอินพุตคือ [5,3,8,9,1,4,6,2] ผลลัพธ์คือ 6

วิธีแก้:

• เริ่มต้น a, b, c ด้วย NULL
• วนลูป i := 0 ถึงขนาด nums - 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