題目

難度：★★☆☆☆
類型：數(shù)組

給定一個(gè)非空數(shù)組，返回此數(shù)組中第三大的數(shù)。如果不存在，則返回?cái)?shù)組中最大的數(shù)。要求算法時(shí)間復(fù)雜度必須是O(n)。

示例

示例 1:
輸入: [3, 2, 1]
輸出: 1
解釋: 第三大的數(shù)是 1.

示例 2:
輸入: [1, 2]
輸出: 2
解釋: 第三大的數(shù)不存在, 所以返回最大的數(shù) 2 .

示例 3:
輸入: [2, 2, 3, 1]
輸出: 1
解釋: 注意，要求返回第三大的數(shù)，是指第三大且唯一出現(xiàn)的數(shù)。
存在兩個(gè)值為2的數(shù)，它們都排第二。

解答

下面是一個(gè)比較容易理解的解法，一趟遍歷的同時(shí)，找到最大、次大和第三大數(shù)。

class Solution:
    def thirdMax(self, nums):
        top1, top2, top3 = float('-inf'), float('-inf'), float('-inf')
        for num in nums:
            if num == top1 or num == top2 or num == top3:   # 遇到相同的數(shù)
                continue                                    # 跳過(guò)
            if num > top1:                                  # 遇到了比三個(gè)數(shù)都大的數(shù)
                top1, top2, top3 = num, top1, top2          # 更新三個(gè)最大數(shù)
            elif num > top2:                                # 基于最大與次大數(shù)之間
                top2, top3 = num, top2                      # 更新后兩個(gè)數(shù)
            elif num > top3:                                # 介于次大和第三大數(shù)之間
                top3 = num                                  # 更新第三大數(shù)
        return top1 if top3 == float('-inf') else top3      # 返回第三大數(shù)或第一個(gè)大數(shù)

也有三趟遍歷進(jìn)行尋找的方式，看上去會(huì)更快一些：

class Solution(object):
    def thirdMax(self, nums):
        top1, top2, top3 = float('-inf'), float('-inf'), float('-inf')
        length = len(nums)

        # 一趟遍歷尋找第一大數(shù)
        for i in range(length):
            if nums[i] > top1:
                top1 = nums[i]

        # 第二趟遍歷尋找次大數(shù)
        for i in range(length):
            if top2 < nums[i] < top1:
                top2 = nums[i]
                
        # 第三趟遍歷尋找第三大數(shù)
        for i in range(length):
            if top3 < nums[i] < top2:
                top3 = nums[i]

        return top1 if top3 == float('-inf') else top3      # 返回第三大數(shù)或第一個(gè)大數(shù)

如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~