【LeetCode】414、第三大的数

414、Third Maximum Number第三大的数

难度：简单

题目描述

• 英文：

  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).

• 中文：

  给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是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.

解题思路

利用三个变量分别记录数组第1、2、3大的数字，遍历一遍数组即可更新前三大的数，时间复杂度O(n)。

引申出的top-k问题，以及解决top-k问题的BFPRT算法，后续再详细记录。

代码提交

Python2，用时28ms，内存11.1M

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        first = second = third = None
        for temp in nums:
            if temp > first:
                first, second, third = temp, first, second
            elif first > temp > second:
                second, third = temp, second
            elif second > temp > third:
                third = temp
        return third if third is not None else first

Tips

None