3.C++力扣刷題414

題目：

給你一個非空數組，傳回此數組中 第三大的數 。如果不存在，則傳回數組中最大的數。

示例：

示例 1：

輸入：[3, 2, 1]

輸出：1

解釋：第三大的數是 1 。

示例 2：

輸入：[1, 2]

輸出：2

解釋：第三大的數不存在, 是以傳回最大的數 2 。

示例 3：

輸入：[2, 2, 3, 1]

輸出：1

解釋：注意，要求傳回第三大的數，是指在所有不同數字中排第三大的數。

此例中存在兩個值為 2 的數，它們都排第二。在所有不同數字中排第三大的數為 1 。

進階：

你能設計一個時間複雜度 O(n) 的解決方案嗎？

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/third-maximum-number

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

個人代碼如下：

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        //不能使用int,使用64位長整型,LONG_MIN是-2的63次方
        long long  FirstMax = LONG_MIN, SecondMax = LONG_MIN,ThirdMax = LONG_MIN;
        /*for(int i=0;i<nums.size();i++){
            if(nums[i] == FirstMax || nums[i] == SecondMax || nums[i] == ThirdMax)
            continue; 
        }*/
        for(auto x :nums){
            //若有一個等于初始值就直接不考慮
            if(x == FirstMax || x == SecondMax || x == ThirdMax) continue;
            //若大于最大值，将x指派給最大值，最大值指派給第二大值，第二大值指派給第三大值
            if(x > FirstMax){
                ThirdMax = SecondMax;
                SecondMax = FirstMax;
                FirstMax = x;
            }
            else if(x > SecondMax){
                ThirdMax = SecondMax;
                SecondMax = x;
            }
            else if(x > ThirdMax){
                ThirdMax = x;
            }
        }
        //若等于初始值則說明不存在第三大的數，直接傳回最大值
        //若不等于初始值則傳回ThirdMax即為第三大值
        return ThirdMax == LONG_MIN ? FirstMax : ThirdMax;
    }
};
           

其他大佬的代碼如下：

//最大堆方法
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        make_heap(nums.begin(),nums.end(),less<int>()); //建立最大堆
        int count = 0;
        int n; //用來檢驗是否出現重複的值
        int first = nums[0];//儲存第一個堆的堆頂值,若第三大的數不存在則傳回這個first值
        n = first;  //同時n也要記錄這個值
        pop_heap(nums.begin(),nums.end(),less<int>()); 
        nums.pop_back();//pop_back()操作要在pop_heap之後,push_back操作要在pop_heap之前  
        count++;
        while(nums.size()>0){
            if(n!=nums[0]){ //當沒有出現重複的頂堆值時更改将n值更改為新頂堆值,并且count++
              count++; 
              n = nums[0]; 
            if(count==3)
            return n;
            }         
            pop_heap(nums.begin(),nums.end(),less<int>());
            nums.pop_back();     
        }
        return first;//沒有找到第三大的數則傳回前面儲存的first值
    }
};
//作者：KarlHarris
//連結：https://leetcode-cn.com/problems/third-maximum-number/solution/414czui-da-dui-si-lu-mei-ci-huo-qu-dui-d-csha/
//來源：力扣（LeetCode）
//著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
           

//set方法
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> cun(nums.begin(),nums.end());
        int n = cun.size();
        if(n<3){
            return *(cun.rbegin());
        }
        set<int>::reverse_iterator it = cun.rbegin();
        it++;
        it++;
        return *it;
    }
};
//作者：alexampe
//連結：https://leetcode-cn.com/problems/third-maximum-number/solution/dai-ma-luo-ji-qing-xi-xin-shou-you-hao-m-np3c/
//來源：力扣（LeetCode）
//著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
           

解題思路：

先利用set集合來去除vector中重複的部分（set預設按照升序進行存放）。判斷set元素個數，三個以下的時候，直接利用反向疊代器輸出最後一個元素。三個及以上的情況，利用反向疊代器輸出第三大的元素。

//直接維護三個變量
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long long  m1 = -3e9, m2 = -3e9, m3 = -3e9;
        for (auto x : nums) {
            if (x == m1 || x == m2 || x == m3) continue;
            if (x > m1) {
                m3 = m2;
                m2 = m1;
                m1 = x;
            } else if (x > m2) {
                m3 = m2;
                m2 = x;
            } else if (x > m3) 
                m3 = x;
        }
        if (m3 == -3e9) return m1;
        else return m3;
    }
};
//作者：wangdh15
//連結：https://leetcode-cn.com/problems/third-maximum-number/solution/wei-hu-san-ge-bian-liang-by-acw_wangdh15/
//來源：力扣（LeetCode）
//著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。