414.Third Maximum Number

Tags: [container], [bucket], [sort]

Link: https://leetcode.com/problems/third-maximum-number/?tab=Description

Given anon-emptyarray of integers, return thethirdmaximum 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: container, bucket, sort

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            raise ValueError('the input is invalid')

        num_set = set()
        rest_container = []
        for num in nums:
            if len(rest_container) == 3:
                break
            if num in num_set:
                continue
            num_set.add(num)
            rest_container.append(num)

        rest_container = sorted(rest_container)
        if len(rest_container) < 3:
            return rest_container[-1]

        for num in nums:
            if num in num_set:
                continue
            num_set.add(num)
            if num > rest_container[0]:
                rest_container[0] = num
                rest_container = sorted(rest_container)

        return rest_container[0]

Note:

• Time complexity = O(n), n is the number of elements in the given array.
• The sorting here costs T = O(1), because the size of the rest_container is constant.