LeetCode 414 Third Maximum Number

mac2022-06-30 33

Problem:

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.

Summary:

找出整形数组中第三大的数，若存在第三大的数则返回该数，否则返回最大的数。

注意所谓的“大”为严格意义上的大于，大于等于的关系不成立。

Solution:

1. 首先将数组从大到小排序，然后从头遍历去掉重复数字，同时用一个指针记录当下去掉重复数字后的索引值。最后判断新数组中数字个数是否大于3即可。

1 class Solution { 2 public: 3 static bool descending (int i, int j) { //自定义排序函数，此处应为static，否则报错 4 return i > j; 5 } 6 7 int thirdMax(vector<int>& nums) { 8 int len = nums.size(); 9 sort(nums.begin(), nums.end(), descending); 10 //sort(nums.begin(). nums.end(), greater<int>()); 11 12 int j = 1; 13 for (int i = 1; i < len; i++) { 14 if(nums[i] < nums[i - 1]) { 15 nums[j] = nums[i]; 16 j++; 17 } 18 } 19 20 return j > 2 ? nums[2] : nums[0]; 21 } 22 };

2. 用set维护当前的三个最大值，由于set有去重和自动从小到大排序的功能，可以再size大于3时去掉最小的，即当前的第四大数。

1 class Solution { 2 public: 3 int thirdMax(vector<int>& nums) { 4 int len = nums.size(); 5 set<int> s; 6 for (int i = 0; i < len; i++) { 7 s.insert(nums[i]); 8 if (s.size() > 3) { 9 s.erase(s.begin()); 10 } 11 } 12 13 return s.size()==3 ? *s.begin() : *s.rbegin(); 14 } 15 };

参考：http://www.cnblogs.com/grandyang/p/5983113.html