Leetcode414

Leetcode414：第三大的数

题目描述

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。
要求算法时间复杂度必须是O(n)。

示例 1:输入: [3, 2, 1]

输出: 1
解释: 第三大的数是 1.

示例 2:
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:
输入: [2, 2, 3, 1]
输出: 1
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。

解法一：基于set的去重排序法

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> a;
        a.insert(nums.cbegin(), nums.cend());
        vector<int> b;
        for (auto n : a)
            b.push_back(n);
        sort(b.begin(), b.end());
        reverse(b.begin(), b.end());
        if (b.size()>2)
            return b[2];
        else
            return b[0];

    }
};

解法二：基于set的有序性和唯一性

/*****************************************************
基于set的有序性和唯一性
利用set中元素的有序性和唯一性，将元素放入set中，
若set的size不小于3输出倒数第三个元素；
若set的size小于3，输出最后一个元素。
****************************************************/
class Solution2 {
public:
    int thirdMax(vector<int>& nums)
    {
        set<int> s(nums.begin(), nums.end()); //基于范围的初始化
        auto it = s.end();  //设置一个迭代器
        it--;
        if (s.size() >= 3) {   //因为set默认是按照升序排序的，所以最后应该返回倒数第三个数
            it--;
            it--;
        }
        return *it;    //迭代器解引用
    }
};

解法三：基于sort排序单标记法

class Solution3 {
public:
    int thirdMax(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int res, flag = 1;
        res = nums[nums.size() - 1];
        for (int i = nums.size() - 2; i >= 0; --i)
        {
            if (res != nums[i] && flag < 3)
            {
                res = nums[i];
                ++flag;
            }
        }
        if (flag == 3)
            return res;
        else
            return nums[nums.size() - 1];
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
    vector<int> nums;
    int Size;
    cout << "请输入数组的大小： " << endl;
    cin >> Size;
    int Currval;
    cout << "请输入数组的元素：" << endl;
    for (int i = 0; i < Size; i++)
    {
        cin >> Currval;
        nums.push_back(Currval);
    }
    Solution answer;
    cout << "数组中第3大的数字为： " << answer.thirdMax(nums) << endl;

    system("pause");
    return 0;
}