数组的遍历 485、495、414、628

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) 的解决方案吗？

思路

方法一：堆排序
略
方法二：set容器排序+去重

class Solution {

public:

    int thirdMax(vector<int>& nums) {

        set<int> s;//排序队列

        for(int i=0;i<nums.size();i++){

            s.insert(nums[i]);

        }

        auto iter = s.end();

        if(s.size()<3) return *(--iter);

        else return *(--(--(--iter)));

    }

};

力扣官方题解

我们可以遍历数组，并用三个变量 aaa、bbb 和 ccc 来维护数组中的最大值、次大值和第三大值，以模拟方法二中的插入和删除操作。为方便编程实现，我们将其均初始化为小于数组最小值的元素，视作「无穷小」。

遍历数组，对于数组中的元素 num：

• 若 num>a，我们将 c 替换为 b，b 替换为 a，a 替换为 num，这模拟了将 num 插入有序集合，并删除有序集合中的最小值的过程；
• 若 a>num>b，类似地，我们将 c 替换为 b，b 替换为 num，a 保持不变；
• 若 b>num>c，类似地，我们将 c 替换为 num，a 和 b 保持不变；
• 其余情况不做处理。

遍历结束后，若 c 仍然为 「无穷小」，则说明数组中不存在三个或三个以上的不同元素，即第三大的数不存在，返回 a，否则返回 c。

class Solution {

public:

    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;

    }

};

另一种不依赖元素范围的做法是，将 a、b 和 c 初始化为空指针或空对象，视作「无穷小」，并在比较大小前先判断是否为空指针或空对象。遍历结束后，若 c 为空，则说明第三大的数不存在，返回 a，否则返回 c。

class Solution {

public:

    int thirdMax(vector<int> &nums) {

        int *a = nullptr, *b = nullptr, *c = nullptr;

        for (int &num : nums) {

            if (a == nullptr || num > *a) {

                c = b;

                b = a;

                a = &num;

            } else if (*a > num && (b == nullptr || num > *b)) {

                c = b;

                b = &num;

            } else if (b != nullptr && *b > num && (c == nullptr || num > *c)) {

                c = &num;

            }

        }

        return c == nullptr ? *a : *c;
    }
};