力扣题目汇总(缺失数字,第三大的数,至少

2023-01-31 00:01:51 汇总 缺失 第三大

缺失数字

1.题目描述

  1. 给定一个包含 0, 1, 2, ..., nn 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

    示例 1:

    输入: [3,0,1]
    输出: 2

    示例 2:

    输入: [9,6,4,2,3,5,7,0,1]
    输出: 8

    说明:
    你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?3.解题

    2.解题思路

#没出现的数字肯定总和剪去给你的列表就是那个数字

3.解题

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums_sum = 0
        for a in range(len(nums)+1):
            nums_sum += a
        return nums_sum-sum(nums)
            

第三大的数

1.题目描述

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

    示例 1:

    输入: [3, 2, 1]
    
    输出: 1
    
    解释: 第三大的数是 1.

    示例 2:

    输入: [1, 2]
    
    输出: 2
    
    解释: 第三大的数不存在, 所以返回最大的数 2 .

    示例 3:

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

2.解题思路

#这题会出现的情况有4种
#长度为1时候,最大就是他本是
#长度为2时候,最大就是他的最大
#长度3的时候,为他最小值及第三大
#长度4我们就对他进行排序取倒数第三就可以了

3.解题

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        nums_set = set(nums)
        if len(nums_set) == 1:  #第一种
            return nums[0]
        elif len(nums_set) ==3: #第二种
            return min(nums_set)
        elif len(nums_set) ==2: #第三种
            return max(nums_set)
        else:        #第四种
            nums_list = list(nums_set)
            nums_list.sort()
            return nums_list[-3]

至少是其他数字两倍的最大数

1题目描述

  • 在一个给定的数组nums中,总是存在一个最大元素 。

    查找数组中的最大元素是否至少是数组中每个其他数字的两倍。

    如果是,则返回最大元素的索引,否则返回-1。

    示例 1:

    输入: nums = [3, 6, 1, 0]
    输出: 1
    解释: 6是最大的整数, 对于数组中的其他整数,
    6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.

    示例 2:

    输入: nums = [1, 2, 3, 4]
    输出: -1
    解释: 4没有超过3的两倍大, 所以我们返回 -1.

2.解题

解题思路:跟着题意走就好了,主要是利用列表的copy

3.解题

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        if len(nums) >=2:
            nums_1= nums.copy()
            nums_1.sort()
            max_1 = nums_1[-1]
            max_2 = nums_1[-2]
            if max_1 >= 2*max_2:
                return nums.index(max_1)
            else:
                return -1
        else:
            return 0

相关文章