LeetCode414-第三大的数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/third-maximum-number/

中文链接：https://leetcode-cn.com/problems/third-maximum-number/

题目详述

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

1
2
3
4
5
输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.

示例 2:

1
2
3
4
5
输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:

1
2
3
4
5
6
输入: [2, 2, 3, 1]

输出: 1

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

题目详解

  • 运用三个变量来表示第一大、第二大、第三大的值。
  • 遍历数组，运用当前元素进行更新。
  • 注意为了正确更新，需要用 long 类型，避免与 int 的数据范围产生冲突。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00414 {

    public int thirdMax(int[] nums) {
        long m1 = Long.MIN_VALUE;
        long m2 = Long.MIN_VALUE;
        long m3 = Long.MIN_VALUE;
        for (int 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;
            }
        }
        return (int) (m3 != Long.MIN_VALUE ? m3 : m1);
    }
}