目录
一、697. 数组的度
二、448. 找到所有数组中消失的数字
三、442. 数组中重复的数据
四、 41. 缺失的第一个正数
五、485. 最大连续 1 的个数
一、697. 数组的度
哈希表
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
# 哈希表
# 找出最大度值第一次出现和最后一次出现的位置
# 最大度值可能不止一个
hash = {}
for i, x in enumerate(nums):
# 记录次数，第一次出现位置，最后一次出现位置
cnt, first, last = hash.get(x, (0, 0, 0))
if cnt == 0:
# 第一次出现
first, last = i, i
cnt += 1
else:
last = i # 更新最近一次出现的位置
cnt += 1
hash[x] = (cnt, first, last)
# 对值进行排序
v = sorted(list(hash.values()), reverse = True)
maxCnt, minLen = v[0][0], v[0][2] - v[0][1]
for i in range(1, len(v)):
# 在最大度值中找最小长度
if v[i][0] != maxCnt:
break
minLen = min(minLen, v[i][2] - v[i][1])
return minLen + 1 #长度是坐标差加一二、448. 找到所有数组中消失的数字
1.哈希表
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
# 哈希表
# 时复O(n)
ans = []
hash = Counter(nums)
n = len(nums)
for i in range(1, n + 1):
if i not in hash.keys():
ans.append(i)
return ans2.集合运算
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
# 集合运算
return list(set(range(1, len(nums) + 1)) - set(nums))3.原地运算，来自官方题解（. - 力扣（LeetCode））。
时复为O(n)，无额外空间。太妙了这个方法。题目中的元素范围信息（属于[ 1, n ]）也很重要。
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
# 原地运算
# 在原数组上运算，相当于一个数组两用
n = len(nums)
for num in nums:
x = (num - 1) % n
# x = num % n - 1 #对于python索引来说是一样的
# 但是还是尽量避免出现负数，比如num == n时
nums[x] += n # 通过使用统一额外的值来表示，起到避免更改原数字且储存信息的作用
ans = [i + 1 for i, x in enumerate(nums) if x <= n]
return ans三、442. 数组中重复的数据
1.原地操作，类比上一题
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
# 原地操作
n = len(nums)
for num in nums:
x = (num - 1) % n
nums[x] += n
return [i + 1 for i, x in enumerate(nums) if x > 2 * n]
# 注意是大于，原值是大于等于1的2.原地操作2，使用正负号标记。来自官方题解（. - 力扣（LeetCode））。
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
# 原地操作2，使用正负号标记
ans = []
for x in nums:
x = abs(x)
if nums[x - 1] > 0:
# x第一次出现
nums[x - 1] = - nums[x - 1]
else:
# x第二次出现
# 最多只会出现两次所以没问题
ans.append(x)
return ans3.原地交换，来自官方题解。
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
# 原地交换
for i in range(len(nums)):
# 让x放第x位
while nums[nums[i] - 1] != nums[i]:
# 第x位不等于x
# 不等代表第一次出现，放到对应位置
# 等代表第二次出现，不用管，任意交换到何处都可
tmp = nums[i] # 此处不要直接进行交换
nums[tmp - 1], nums[i] = nums[i], nums[tmp - 1]
return [x for i, x in enumerate(nums) if x - 1 != i]这里使用tmp的原因来自评论（. - 力扣（LeetCode））。
四、 41. 缺失的第一个正数
不会，来自官方题解（. - 力扣（LeetCode））。本质是要抓住“对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1, N+1] 中。”，再将数字范围进行限制，转化为之前做过的题型。
1.原地哈希
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
# 对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1, N+1] 中
# 哈希表
# 将无限制改为有限制
n = len(nums)
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
# 做标记
for x in nums:
x = abs(x)
if x <= n:
# 只需要管该区域
if nums[x - 1] > 0:
nums[x - 1] *= -1
for i, x in enumerate(nums):
if x > 0:
return i + 1
return n + 12.原地置换
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
# 对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1, N+1] 中
# 原地置换
n = len(nums)
for i in range(n):
# 只将需要放回原位的值放回即可
while nums[i] > 0 and nums[i] <= n and nums[nums[i] - 1] != nums[i]:
x = nums[i]
nums[x - 1], nums[i] = nums[i], nums[x - 1]
for i, x in enumerate(nums):
if x - 1 != i:
return i + 1
return n + 1五、485. 最大连续 1 的个数
1.滑动窗口
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
# 滑动窗口
n = len(nums)
ans = 0
l, r = 0, 0
while l < n:
while r < n and nums[l] == nums[r]:
r += 1
if nums[l] == 1:
# 中间都为1时更新
ans = max(ans, r - l)
l = r # 直接跳转，中间都是相同的
return ans2.一次遍历，来自官方题解（. - 力扣（LeetCode））。
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
# 一次遍历
maxCnt, cnt = 0, 0
for x in nums:
if x == 1:
cnt += 1
else:
# 更新
maxCnt = max(maxCnt, cnt)
cnt = 0
# 最后一位
maxCnt = max(maxCnt, cnt)
return maxCnt完
感谢你看到这里！一起加油吧！
