Third Maximum Number

Posted on | Edited on | | Views:

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)$, 意味着, 不能排序.

思路

先把数组去重, 然后个数少于3的直接返回最大值. 然后维护一个长度为3的tops数组, 从左往右扫描, 然后个扫到的值更新到tops数组里面.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def thirdMax(nums):
    nums = list(set(nums))
    if len(nums) < 3:
        return max(nums)
    tops = [-float('inf')] * 3
    
    for num in nums:
        tops = swap(tops, num)

    return tops[2]

def swap(nums, n):
    if n > tops[0]:
        tops[2] = tops[1]
        tops[1] = tops[0]
        tops[0] = n
    elif n > tops[1]:
        tops[2] = tops[1]
        tops[1] = n
    elif n > tops[2]:
        tops[2] = n
    return tops