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.
C Solution:
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int thirdMax(int* nums, int numsSize) {
if (numsSize == 1) return nums[0];
if (numsSize == 2) return MAX(nums[0], nums[1]);
int res[3];
res[0] = nums[0];
int i;
for (i = 1; i < numsSize && nums[i] == res[0]; i++);
if (i == numsSize) return res[0];
res[1] = nums[i];
for (; i < numsSize && (nums[i] == res[0] || nums[i] == res[1]); i++);
if (i == numsSize) return MAX(res[0], res[1]);
res[2] = nums[i];
if (res[0] < res[1]) {
res[0] ^= res[1];
res[1] ^= res[0];
res[0] ^= res[1];
}
if (res[1] < res[2]) {
res[1] ^= res[2];
res[2] ^= res[1];
res[1] ^= res[2];
}
if (res[0] < res[1]) {
res[0] ^= res[1];
res[1] ^= res[0];
res[0] ^= res[1];
}
for (; i < numsSize; i++) {
if (nums[i] > res[0]) {
res[2] = res[1];
res[1] = res[0];
res[0] = nums[i];
continue;
}
if (nums[i] == res[0]) continue;
if (nums[i] > res[1]) {
res[2] = res[1];
res[1] = nums[i];
continue;
}
if (nums[i] == res[1]) continue;
if (nums[i] > res[2]) {
res[2] = nums[i];
}
}
return res[2];
}
Python Solution:
class Solution(object):
def thirdMax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 3: return max(nums)
origin_max = _max = max(nums)
for _ in range(2):
tmp = None
for num in nums:
if num < _max:
if tmp is None:
tmp = num
else:
tmp = max(tmp, num)
if tmp is None: return origin_max
_max = tmp
return _max
Summary:
- Straightforward, best way.
LeetCode: 414. Third Maximum Number
近期评论