414.第三大的数

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

示例 1：

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

示例 2：

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

又要排序，又要独一无二，可以说是为TreeSet量身定做的题

也可以用三个变量进行模拟，初始为最小值的思路避免了很多麻烦

Solution：有序集合

因为是直接返回的数，使用TreeSet的性质

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int thirdMax(int[] nums) {
        TreeSet<Integer> s = new TreeSet<Integer>();
        for (int num : nums) {
            s.add(num);
            if (s.size() > 3) {
                s.remove(s.first());
            }
        }
        return s.size() == 3 ? s.first() : s.last();
    }
}

Solution1：三个变量

我们可以遍历数组，并用三个变量 a、b 和 c 来维护数组中的最大值、次大值和第三大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    // thirdMax方法接收一个整数数组nums作为参数，返回数组中第三大的数
    public int thirdMax(int[] nums) {
        // 初始化三个变量a、b、c来分别存储最大的、第二大的和第三大的数
        // 使用Long.MIN_VALUE以便处理整数数组中所有可能的值
        long a = Long.MIN_VALUE, b = Long.MIN_VALUE, c = Long.MIN_VALUE;
        // 遍历数组中的每个元素
        for (long num : nums) {
            // 如果当前元素大于a，则更新a、b、c的值
            if (num > a) {
                c = b;
                b = a;
                a = num;
            // 如果当前元素介于a和b之间，则更新b、c的值
            } else if (a > num && num > b) {
                c = b;
                b = num;
            // 如果当前元素介于b和c之间，则更新c的值
            } else if (b > num && num > c) {
                c = num;
            }
        }
        // 如果c仍然是Long.MIN_VALUE，说明不存在第三大的数，返回a（最大的数）
        // 否则，返回c（第三大的数）
        return c == Long.MIN_VALUE ? (int) a : (int) c;
    }
}