[Array]414. Third Maximum Number

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.

Both numbers with value 2 are both considered as second maximum.
思路：找出一个数组中第三大的元素，这里只是说integer，没有规定范围，因此应该考虑到int型的最大值和最小值，INT_MIN，INT_MAX,
自己的想法：（129ms）比较简单，使用额外的辅助空间，将不重复的元素排序

 int thirdMax(vector<int>& nums) {

         sort(nums.begin(),nums.end());

         vector<int> ans;

         int i;

         for(i=nums.size()-;i>=;--i)

         {

             if(find(ans.begin(),ans.end(),nums[i])==ans.end())//一开始自己的想法是进行排序，然后相邻元素是否相等，

                 ans.push_back(nums[i]);

         }

         if(ans.size()<)

             return ans[];

         return ans[];

     }

或者这样：

优秀代码：（6ms）既然要找出第三大的元素值，则首先设定三个最小值，然后遍历所有的元素，找出前三大的元素值

 int thirdMax(vector<int>& nums) {

        long long  a, b, c;

         a = b = c = LONG_MIN  ;

         for(auto num : nums){

             if(num <= c || num ==b || num == a)

                 continue;

             else

                 c = num;

             if(c > b)

                 swap(b, c);

             if(b > a)

                 swap(a, b);

         }

         return c == LONG_MIN ? a : c;

     }

函数set下的代码：

 int thirdMax(vector<int>& nums) {

         set<int> top;

         for (auto i : nums) {

             top.insert(i);

             if (top.size() > ) top.erase(top.begin());

         }

         return top.size() ==  ? *top.begin() : *top.rbegin();

     }

set参考链接：http://www.cnblogs.com/BeyondAnyTime/archive/2012/08/13/2636375.html

巴特西

[Array]414. Third Maximum Number

最新文章

热门文章