【LeetCode】414. 第三大的数

414. 第三大的数

难度：简单

题目

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

示例 1：

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

示例 2：

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

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

提示：

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

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

个人题解

思路：

用三个变量分别装最大，第二大，第三大的数，一次遍历即可，就是要注意条件

class Solution {public int thirdMax(int[] nums) {Integer[] maxArr = new Integer[3];for (int num : nums) {if (maxArr[0] == null || num > maxArr[0]) {maxArr[2] = maxArr[1];maxArr[1] = maxArr[0];maxArr[0] = num;} else if (num != maxArr[0] && (maxArr[1] == null || num > maxArr[1])) {maxArr[2] = maxArr[1];maxArr[1] = num;} else if (num != maxArr[0] && num != maxArr[1] && (maxArr[2] == null || num > maxArr[2])) {maxArr[2] = num;}}return maxArr[1] == null || maxArr[2] == null ? maxArr[0] : maxArr[2];}
}

复杂度分析 ：

时间复杂度：O(n)
空间复杂度：O(1)

官方题解

方法一：排序

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

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

复杂度分析 ：

时间复杂度：O(n log⁡n)
空间复杂度：O(log⁡n)

方法二：有序集合

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

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

复杂度分析 ：

时间复杂度：O(n)
空间复杂度：O(1)

方法三：一次遍历

class Solution {public int thirdMax(int[] nums) {long a = Long.MIN_VALUE, b = Long.MIN_VALUE, c = Long.MIN_VALUE;for (long num : nums) {if (num > a) {c = b;b = a;a = num;} else if (a > num && num > b) {c = b;b = num;} else if (b > num && num > c) {c = num;}}return c == Long.MIN_VALUE ? (int) a : (int) c;}
}

class Solution {public int thirdMax(int[] nums) {Integer a = null, b = null, c = null;for (int num : nums) {if (a == null || num > a) {c = b;b = a;a = num;} else if (a > num && (b == null || num > b)) {c = b;b = num;} else if (b != null && b > num && (c == null || num > c)) {c = num;}}return c == null ? a : c;}
}

复杂度分析 ：

时间复杂度：O(n)
空间复杂度：O(1)

作者：力扣官方题解
链接：https://leetcode.cn/problems/third-maximum-number/solutions/1032401/di-san-da-de-shu-by-leetcode-solution-h3sp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。