LeetCode 414.Third Maximum Number

LeetCode 414.Third Maximum Number

Description:

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.

---

分析：

首先，我们先给输入的数组按从小到大排序
然后，从大到小循环遍历数组，判断相连两个数是否相等，若不等，维护当前遍历到达的数组位置，记为temp，并且更新cnt（cnt表示已有多少对不等的相邻数）
最后，若cnt等于2时，更新flag标记为false，表示已找到第三大的数，退出循环，返回结果；若循环结束后flag依然为true；表示未找到第三大的数，返回最大数。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
	int thirdMax(vector<int>& nums) {
		int size = nums.size();
		sort(nums.begin(), nums.end());
		bool flag = true;
		int temp = 0, cnt = 0;
		for (int i = size - 1; i > 0; i--) {
			if (nums[i] != nums[i - 1]) {
				temp = i - 1;// 记录下当前循环到达的位置
				cnt++;
				if (cnt == 2) {// 表示从大到小已有两个数不相等，即找到第三大的数
					flag = false;
					break;
				}
			}
		}
		if (flag) {// 表示未找到第三大的数，因此返回最大的数
			return nums[size - 1];
		}
		else {
			return nums[temp];
		}
	}
};
int main() {
	Solution s;
	vector<int> nums;
	int n, num;
	cin >> n;
	while (n-- > 0) {
		cin >> num;
		nums.push_back(num);
	}
	cout << s.thirdMax(nums) << endl;
	return 0;
}

分析：

看了一下LeetCode上面的讨论，也可以用集合的方法来解决这道题，首先创建一个set，用来存放遍历得到的数，将数组中的每一个数都插入到set中（当然利用到set的属性：集合中的元素不能重复），同时判断set的大小维持插入到set中数的个数只有3个，最后判断set大小是否等于3，若等于3，则返回set的第一个数，反之返回最后一个数（也就是最大的数）。

代码如下：

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
public:
	int thirdMax(vector<int>& nums) {
		set<int> top3;
		for (int num : nums) {
			top3.insert(num);
			if (top3.size() > 3)
				top3.erase(top3.begin());
		}
		return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
	}
};
int main() {
	Solution s;
	vector<int> nums;
	int n, num;
	cin >> n;
	while (n-- > 0) {
		cin >> num;
		nums.push_back(num);
	}
	cout << s.thirdMax(nums) << endl;
	return 0;
}