จำนวนสูงสุดที่สามใน C++

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

ดังนั้น หากอินพุตเป็น [5,3,8,9,1,4,6,2] ผลลัพธ์จะเป็น 6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เริ่มต้น a, b, c ด้วย NULL

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ nums ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้า a เป็นโมฆะหรือ nums[i]>=ค่าของ a แล้ว −

    • ถ้าไม่ใช่ค่า null และ nums[i]> ค่าของ a แล้ว −

      • ค :=ข, ข :=ก

    • a :=nums[i]

  • มิฉะนั้นเมื่อ b เป็นโมฆะหรือ nums[i]>=ค่าของ b แล้ว −

    • ถ้า b ไม่เป็นโมฆะและ nums[i]> ค่าของ b แล้ว −

      • ค :=ข

    • b :=nums[i]

  • มิฉะนั้น เมื่อ c เป็นโมฆะหรือ nums[i]>=ค่าของ c แล้ว −

    • c :=nums[i]

• คืนค่า (ถ้า c เป็นค่าว่าง แสดงว่าค่าของ 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