class Solution {
public:
int thirdMax(vector<int>& nums) {
}
};
414. 第三大的数
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 1：
输入：[3, 2, 1] 输出：1 解释：第三大的数是 1 。
示例 2：
输入：[1, 2] 输出：2 解释：第三大的数不存在, 所以返回最大的数 2 。
示例 3：
输入：[2, 2, 3, 1] 输出：1 解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
提示：
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
相似题目
原站题解
javascript 解法, 执行用时: 64 ms, 内存消耗: 41.2 MB, 提交时间: 2023-09-27 15:06:12
/**
* @param {number[]} nums
* @return {number}
*/
var thirdMax = function(nums) {
nums.sort((a, b) => a - b);
nums.reverse();
for (let i = 1, diff = 1; i < nums.length; ++i) {
if (nums[i] !== nums[i - 1] && ++diff === 3) { // 此时 nums[i] 就是第三大的数
return nums[i];
}
}
return nums[0];
};
golang 解法, 执行用时: 8 ms, 内存消耗: 2.8 MB, 提交时间: 2023-09-27 15:05:58
func thirdMax(nums []int) int {
sort.Sort(sort.Reverse(sort.IntSlice(nums)))
for i, diff := 1, 1; i < len(nums); i++ {
if nums[i] != nums[i-1] {
diff++
if diff == 3 { // 此时 nums[i] 就是第三大的数
return nums[i]
}
}
}
return nums[0]
}
// 有序集合
func thirdMax2(nums []int) int {
t := redblacktree.NewWithIntComparator()
for _, num := range nums {
t.Put(num, nil)
if t.Size() > 3 {
t.Remove(t.Left().Key)
}
}
if t.Size() == 3 {
return t.Left().Key.(int)
}
return t.Right().Key.(int)
}
java 解法, 执行用时: 3 ms, 内存消耗: 41.9 MB, 提交时间: 2023-09-27 15:05:28
class Solution {
// 有序集合
public int thirdMax2(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();
}
// 排序
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--;
}
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 9.4 MB, 提交时间: 2023-09-27 15:04:40
class Solution {
public:
// 排序
int thirdMax(vector<int> &nums) {
sort(nums.begin(), nums.end(), greater<>());
for (int i = 1, diff = 1; i < nums.size(); ++i) {
if (nums[i] != nums[i - 1] && ++diff == 3) { // 此时 nums[i] 就是第三大的数
return nums[i];
}
}
return nums[0];
}
// 有序集合
int thirdMax2(vector<int> &nums) {
set<int> s;
for (int num : nums) {
s.insert(num);
if (s.size() > 3) {
s.erase(s.begin());
}
}
return s.size() == 3 ? *s.begin() : *s.rbegin();
}
};
python3 解法, 执行用时: 68 ms, 内存消耗: 17 MB, 提交时间: 2023-09-27 15:03:40
from sortedcontainers import SortedList
class Solution:
def thirdMax(self, nums: List[int]) -> int:
s = SortedList()
for num in nums:
if num not in s:
s.add(num)
if len(s) > 3:
s.pop(0)
return s[0] if len(s) == 3 else s[-1]
python3 解法, 执行用时: 44 ms, 内存消耗: 16.6 MB, 提交时间: 2023-09-27 15:03:29
class Solution:
def thirdMax(self, nums: List[int]) -> int:
nums.sort(reverse=True)
diff = 1
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
diff += 1
if diff == 3: # 此时 nums[i] 就是第三大的数
return nums[i]
return nums[0]
python3 解法, 执行用时: 48 ms, 内存消耗: 17.4 MB, 提交时间: 2023-09-27 15:02:59
class Solution:
def thirdMax(self, nums: List[int]) -> int:
nums = list(set(nums))
nums.sort()
if len(nums) < 3:
return nums[-1]
return nums[-3]
python3 解法, 执行用时: 44 ms, 内存消耗: N/A, 提交时间: 2018-09-26 21:34:11
class Solution:
def thirdMax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = list(set(nums))
nums.sort()
if len(nums) < 3:
return nums[-1]
return nums[-3]