找出数组中第K大的数，时间复杂度O（n）

通常在K比较小的时候，第一思路是进行K次循环，找出第一大、第二大。。。一直到第K大。这思路当然是没有问题，但是时间复杂度较高，而且K一旦太大，就不太适用了。

可以用vector数组降序存储K个元素，符合条件的加入数组中：（K=3）

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        vector<int> ans;
        for(auto n : nums){
            bool bSame=false;
            for(auto a : ans){
                if(n == a){
                    bSame=true;
                    break;
                }
            }
            if(bSame) continue;

            for(int i=0;i<ans.size();i++){
                if(n>ans[i]){
                    swap(n,ans[i]);
                }
            }

            if(ans.size()<3){
                ans.push_back(n);
            }
        }
        if(ans.empty()) return 0;
        if(ans.size()<3) return ans.front();
        return ans.back();
    }
};
           

1、使用 vector ans 来记录最大的三个数

2、根据题意，相同数字不占排名，所以遇到相同数字直接跳过

3、再从头比到尾，如果新数字够大，就交换

4、如果 ans 还不到 3 个，就加入

5、输出结果的时候，根据题意，有第三输出第三，没第三输出第一，如果第一也没有安全一点输出 0