题目:268. 缺失数字
链接:https://leetcode-cn.com/problems/missing-number
问题:
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。 示例 1: 输入: [3,0,1] 输出: 2 示例 2: 输入: [9,6,4,2,3,5,7,0,1] 输出: 8 说明: 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
解题:
1、求和相减。分别求得1+2+...+n的和,以及数组的和,两者相减就是缺失的数。
2、排序遍历。对数组排序后,下标和元素不相等的地方,就是缺失的数;如果所有下标和元素都相等,则缺失的是n。
代码:
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 1、求和相减
# return sum(range(len(nums) + 1)) - sum(nums)
# 2、排序遍历
nums.sort()
for i, n in enumerate(nums):
if i != n:
return i
return len(nums)
PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。
PPS:还是得日更呀,总结一下总是好的。