LeetCode第一天（414.第三大的数）

方法一：排序
将数组从大到小排序后，从头开始遍历数组，通过判断相邻元素是否不同，来统计不同元素的个数。如果能找到三个不同的元素，就返回第三大的元素，否则返回最大的元素。

Arrays.sort 是一个 Java 中的静态方法，用于对数组进行排序。它接受一个数组作为参数，并按照数组元素的自然顺序进行排序。Arrays.sort(nums);

reverse()方法用于对一个容器（如数组、列表或字符串）中的元素进行逆序操作，将其按照相反的顺序重新排列。
reverse(nums);

class Solution {
    public int thirdMax(int[] nums) {
        Arrays.sort(nums);
        reverse(nums);
        for (int i = 1, diff = 1; i < nums.length; ++i) {
            if (nums[i] != nums[i - 1] && ++diff == 3) { // 此时 nums[i] 就是第三大的数
                return nums[i];
            }
        }
        return nums[0];
    }

    public void reverse(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

方法二：有序集合
我们可以遍历数组，同时用一个有序集合来维护数组中前三大的数。具体做法是每遍历一个数，就将其插入有序集合，若有序集合的大小超过 3，就删除集合中的最小元素。这样可以保证有序集合的大小至多为 3，且遍历结束后，若有序集合的大小为 3，其最小值就是数组中第三大的数；若有序集合的大小不足 3，那么就返回有序集合中的最大值。

TreeSet<Integer> 是一个 Java 中的集合类，它实现了 Set 接口，并使用基于红黑树的数据结构来存储元素。在这个特定的情况下，TreeSet<Integer> 是一个整型（Integer）元素的有序集合，它按照元素的自然顺序进行排序。

以下是关于 TreeSet<Integer> 的一些解释：

1. 有序性： TreeSet<Integer> 中的元素按照升序进行排序。这意味着当你向 TreeSet<Integer> 中添加元素时，它们将被自动排序。

2. 去重性： TreeSet<Integer> 不允许重复的元素。如果你尝试向 TreeSet<Integer> 中添加已经存在的元素，那么该元素将不会被重复添加。

3. 基于红黑树： TreeSet<Integer> 内部使用红黑树这种自平衡的二叉搜索树数据结构来存储元素。这种数据结构能够提供高效的插入、删除和查找操作，使得 TreeSet<Integer> 在大多数情况下具有较快的性能。

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();
    }
}