缺失数字
1.题目描述
-
给定一个包含
0, 1, 2, ..., n中 n 个数的序列，找出 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.题目描述
-
给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是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.解题
解题思路:跟着题意走就好了,主要是利用列表的copy3.解题
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