leetcode-414-第三大的数

题目描述

给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例

  • 示例 1:

    1
    2
    3
    4
    5
    输入: [3, 2, 1]

    输出: 1

    解释: 第三大的数是 1.
  • 示例 2:

    1
    2
    3
    4
    5
    输入: [1, 2]

    输出: 2

    解释: 第三大的数不存在, 所以返回最大的数 2 .
  • 示例 3:

    1
    2
    3
    4
    5
    6
    输入: [2, 2, 3, 1]

    输出: 1

    解释: 注意,要求返回第三大的数,是指第三大且唯一出现的数。
    存在两个值为2的数,它们都排第二。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/robot-return-to-origin


  • 解题思路

    首先用苯办法,定义一个最大长度为三的有序列表,依次从nums列表中取值,插入该有序列表。

    优点是节约内存, 缺点是判断比较麻烦。

  • 题解1:

    执行用时:80 ms, 在所有 Python3 提交中击败了21.76%的用户

    内存消耗:14.4 MB, 在所有 Python3 提交中击败了92.21%的用户

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    from typing import List
    class Solution:
    def thirdMax(self, nums: List[int]) -> int:
    # 默认右边最大
    th = []
    while nums:
    num = nums.pop()
    if num in th:
    continue
    if not th:
    th.append(num)
    if len(th) == 1:
    if num > th[0]:
    th.append(num)
    elif num < th[0]:
    th.insert(0, num)
    # 这里需要注意, 第二次因为没有continue.会执行到下面的判断,低级错误。
    continue
    if len(th) == 2:
    if num > th[1]:
    th.append(num)
    elif num < th[0]:
    th.insert(0, num)
    elif num > th[0]:
    th.insert(1, num)
    continue
    if len(th) == 3:
    if num > th[2]:
    th.append(num)
    del th[0]
    elif num < th[0]:
    continue
    elif num > th[0] and num < th[1]:
    del th[0]
    th.insert(0, num)
    elif num > th[1] and num < th[2]:
    del th[0]
    th.insert(1, num)
    continue
    # 这里需要注意, 第一次提交下标写的是2,没有考虑到1的情况,要用反向索引-1
    return th[-1] if len(th) < 3 else th[0]
文章作者: Spaceack
文章链接: http://spaceack.com/2020/09/04/2020-09-04-leetcode-414-%E7%AC%AC%E4%B8%89%E5%A4%A7%E7%9A%84%E6%95%B0/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 丸子家的小云吞
支付宝打赏
微信打赏