414. 第三大的数

Posted on | In
Words count in article: 390 | Reading time ≈ 1

题目

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

示例1：

1
2
3
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1.

示例2：

1
2
3
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .

示例3：

1
2
3
4
输入: [2, 2, 3, 1]
输出: 1
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。

提示：

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

解法

解法一：

用三个变量first, second, third来分别保存第一大，第二大，和第三大的数，然后我们遍历数组，如果遍历到的数字大于当前第一大的数first，那么三个变量各自错位赋值，如果当前数字大于second，小于first，那么就更新second和third，如果当前数字大于third，小于second，那就只更新third，注意这里有个坑，就是初始化要用长整型long的最小值，否则当数组中有Integer.MIN_VALUE存在时，程序就不知道该返回Integer.MIN_VALUE还是最大值first了

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int thirdMax(int[] nums) {
    long first = Long.MIN_VALUE;
    long second = Long.MIN_VALUE;
    long third = Long.MIN_VALUE;
    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 (int) ((Long.MIN_VALUE == third || second == third) ? first : third);
}
0%