Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/414.html
414. Third Maximum Number
Level
Easy
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
Use three variables to store the three distinct maximum numbers. Also use a variable to store the count of distinct numbers in the array. Initially, the three variables for three maximum numbers are Long.MIN_VALUE, where data type long is used to avoid overflow.
Loop over the array. Use the idea of insertion sort and update the three distinct maximum numbers. If the current number is greater than at least one of the three distinct maximum numbers, then update the distinct maximum numbers that has a smaller value, and increase the counter by 1.
Finally, if the counter is greater than or equal to 3, return the third distinct maximum number. Otherwise, return the first maximum number.
-
class Solution { public int thirdMax(int[] nums) { if (nums == null || nums.length == 0) return 0; long firstMax = Long.MIN_VALUE; long secondMax = Long.MIN_VALUE; long thirdMax = Long.MIN_VALUE; int count = 0; for (int num : nums) { long numLong = (long) num; if (numLong == firstMax || numLong == secondMax || numLong == thirdMax) continue; if (numLong > firstMax) { thirdMax = secondMax; secondMax = firstMax; firstMax = numLong; count++; } else if (numLong > secondMax) { thirdMax = secondMax; secondMax = numLong; count++; } else if (numLong > thirdMax) { thirdMax = numLong; count++; } } return count >= 3 ? (int) thirdMax : (int) firstMax; } } -
class Solution: def thirdMax(self, nums: List[int]) -> int: m1 = m2 = m3 = -inf for num in nums: if num in [m1, m2, m3]: continue if num > m1: m3, m2, m1 = m2, m1, num elif num > m2: m3, m2 = m2, num elif num > m3: m3 = num return m3 if m3 != -inf else m1 ############ class Solution(object): def thirdMax(self, nums): """ :type nums: List[int] :rtype: int """ first = second = third = float("-inf") for num in nums: if num in [first, second, third]: continue if num > first: third = second second = first first = num elif num > second: third = second second = num elif num > third: third = num return third if third != float("-inf") else first -
class Solution { public: int thirdMax(vector<int>& nums) { long m1 = LONG_MIN, m2 = LONG_MIN, m3 = LONG_MIN; for (int num : nums) { if (num == m1 || num == m2 || num == m3) continue; if (num > m1) { m3 = m2; m2 = m1; m1 = num; } else if (num > m2) { m3 = m2; m2 = num; } else if (num > m3) { m3 = num; } } return (int) (m3 != LONG_MIN ? m3 : m1); } }; -
func thirdMax(nums []int) int { m1, m2, m3 := math.MinInt64, math.MinInt64, math.MinInt64 for _, num := range nums { if num == m1 || num == m2 || num == m3 { continue } if num > m1 { m3, m2, m1 = m2, m1, num } else if num > m2 { m3, m2 = m2, num } else if num > m3 { m3 = num } } if m3 != math.MinInt64 { return m3 } return m1 }