Problem
https://leetcode.com/problems/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.
Solution: Set
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua // Running time: 9 ms class Solution { public: int thirdMax(vector<int>& nums) { set<int> s; for (int num : nums) { s.insert(num); if (s.size() > 3) s.erase(s.begin()); } return s.size() != 3 ? *s.rbegin() : *s.begin(); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 |
""" Author: Huahua Running time: 52 ms """ class Solution: def thirdMax(self, nums): s = set() for num in nums: s.add(num) if len(s) > 3: s.remove(min(s)) return min(s) if len(s) == 3 else max(s) |