414. 第三大的数

题目

image-20240909133957009

解法

三种解法

  1. 排序
  2. 有序集合
  3. 一次遍历

排序

非常常规且容易想到的解法，只不过在时间复杂度上不是很友好

1
2
3
4
5
6
7
8
9
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];
    }

有序集合

长时间没有使用Set，甚至忘记了有这东西，第一时间先到的是双端队列这种东西，set会对插入的内容进行一个排序处理，begin位置的在默认情况下是最小值

时间复杂度：O(n)，其中 n 是数组 nums 的长度。由于有序集合的大小至多为 3，插入和删除的时间复杂度可以视作是 O(1) 的，因此时间复杂度为 O(n)。

空间复杂度：O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
set<int> s;
for (int x : nums)
{
	s.insert(x);
	if (s.size() > 3)
	{
		s.erase(s.begin());
	}
 
}
 
return s.size() == 3 ? *s.begin() : *s.rbegin();

一次排序

这种实际需要重点学习的方法

这方法实际是对有序集合排序过程的模仿，最开始没有想到这种解决办法是因为max和min这俩函数用多了

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
  • 空间复杂度：O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int thirdMax(vector<int> &nums) {
       long a = LONG_MIN, b = LONG_MIN, c = LONG_MIN;
       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 ? a : c;
   }