LeetCode--414. 第三大的数(C++描述)

刺骨的言语ヽ痛彻心扉 2022-08-28 09:44 162阅读 0赞

// Source : https://leetcode-cn.com/problems/third-maximum-number/submissions/  
// Date : 2021-10-6

题目描述：给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 1：

输入：\[3, 2, 1\]  
输出：1  
解释：第三大的数是 1 。  
示例 2：

输入：\[1, 2\]  
输出：2  
解释：第三大的数不存在, 所以返回最大的数 2 。  
示例 3：

输入：\[2, 2, 3, 1\]  
输出：1  
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。  
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

提示：

1 <= nums.length <= 104  
\-231 <= nums\[i\] <= 231 - 1

题目分析：将数组从大到小排序，然后利用计数器记录是否找到了第三大数字，因为可能存在同一个元素多次出现，此时第三大就需要向后找直到找到不相同的元素，否则就说明该数组元素不足三个，直接返回排序结束后的第一个元素即可。

代码：

class Solution {
        
    public:
        int thirdMax(vector<int>& nums) {
        
            //greater：从大到小排序
            sort(nums.begin(), nums.end(), greater<>());
            for (int i = 1, count = 1; i < nums.size(); ++i) {
        
                if (nums[i] != nums[i - 1] && ++count == 3) {
         
                    // 此时 nums[i] 就是第三大的数
                    return nums[i];
                }
            }
            //如果上面没有返回说明元素不够3个，则直接返回第一个元素
            return nums[0];
    
            // if(nums.size() < 3)
            //     //如果元素个数小于三个，直接返回最大数
            //     return nums[nums.size() - 1];
            // else if(nums.size() == 3)
            //     return nums[0];
            // else
            // {
        
            //     //"删除"相邻的重复元素
            //     vector<int>::iterator new_end = unique(nums.begin(), nums.end());
    	    //     //删除(真正的删除)重复的元素
            //     nums.erase(new_end, nums.end());
            // }
            // return nums[nums.size() - 3];
        }
    };