Easy

题目描述

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

示例 1：

输入：nums = [3,2,1]
输出：1
解释：
第一大的数是 3 。
第二大的数是 2 。
第三大的数是 1 。

示例 2：

输入：nums = [1,2]
输出：2
解释：
第一大的数是 2 。
第二大的数是 1 。
第三大的数不存在，所以返回最大的数 2 。

示例 3：

输入：nums = [2,2,3,1]
输出：1
解释：
第一大的数是 3 。
第二大的数是 2（两个 2 都算作第二大）。
第三大的数是 1 。

提示：

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

**进阶：**你能设计一个时间复杂度 O(n) 的解决方案吗？

解题思路

这道题要求找到数组中第三大的不同数字，如果不存在则返回最大值。

解法一：排序法 最直观的方法是先排序，然后找第三大的不同元素。先对数组进行降序排序，然后遍历找到第三个不同的数字。时间复杂度为 O(n log n)。

解法二：一次遍历维护三个最大值（推荐） 我们可以用三个变量来维护当前遇到的前三大的不同数字：first（最大）、second（第二大）、third（第三大）。遍历数组时：

  • 如果当前数字比 first 大，则更新三个变量
  • 如果当前数字比 second 大但不等于 first，则更新 second 和 third
  • 如果当前数字比 third 大但不等于前两者，则更新 third

需要注意的是，要使用 long 类型来避免整数溢出问题，并且初始化为 LONG_MIN。

最后检查是否找到了三个不同的数字，如果找到了返回 third，否则返回 first。

这种方法只需要一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
        
        for (int num : nums) {
            if (num > first) {
                third = second;
                second = first;
                first = num;
            } else if (num > second && num < first) {
                third = second;
                second = num;
            } else if (num > third && num < second) {
                third = num;
            }
        }
        
        return third == LONG_MIN ? first : third;
    }
};

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        first = second = third = float('-inf')
        
        for num in nums:
            if num > first:
                third, second, first = second, first, num
            elif num > second and num < first:
                third, second = second, num
            elif num > third and num < second:
                third = num
        
        return third if third != float('-inf') else first

public class Solution {
    public int ThirdMax(int[] nums) {
        long first = long.MinValue, second = long.MinValue, third = long.MinValue;
        
        foreach (int num in nums) {
            if (num > first) {
                third = second;
                second = first;
                first = num;
            } else if (num > second && num < first) {
                third = second;
                second = num;
            } else if (num > third && num < second) {
                third = num;
            }
        }
        
        return third == long.MinValue ? (int)first : (int)third;
    }
}

var thirdMax = function(nums) {
    let first = -Infinity, second = -Infinity, third = -Infinity;
    
    for (let num of nums) {
        if (num === first || num === second || num === third) continue;
        
        if (num > first) {
            third = second;
            second = first;
            first = num;
        } else if (num > second) {
            third = second;
            second = num;
        } else if (num > third) {
            third = num;
        }
    }
    
    return third === -Infinity ? first : third;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
一次遍历维护三个最大值O(n)O(1)
排序法O(n log n)O(1)

相关题目