发布时间:2022-08-19 12:58
解题思路:
利用数据结构特点,容易想到使用哈希表(Set)记录数组的各个数字,当查找到重复数字则直接返回
注:可以查找学习一下python中的set()函数用法
算法流程:
1.初始化: 新建 HashSet ,记为 dic
2.遍历数组 nums 中的每个数字 num :
当 num 不在 dic 中,将 num 添加至 dic 中
当 num 在 dic 中,说明重复,直接返回 num ;
class Solution:
def findRepeatNumber(self, nums: [int]) -> int:
dic = set()
for num in nums:
if num not in dic: dic.add(num)
else: return num
解题思路:二分查找
(二分查找的方法之前博客文章有写)
class Solution:
def search(self, nums: List[int], target: int) -> int:
if target not in nums: return 0
left = 0
right = len(nums) - 1
while left <= right:
if nums[left] != target: left += 1
if nums[right] != target: right -= 1
if nums[left] == target and nums[right] == target:
return right - left + 1
解题思路1:遍历每个索引
class Solution:
def missingNumber(self, nums: List[int]) -> int:
for i in range(len(nums)):
if i != nums[i]: return i
return len(nums)
解题思路2:双指针二分查找
根据题意,数组可以按照以下规则划分为两部分。
左子数组: nums[i] = i
右子数组: nums[i] != i
缺失的数字等于 “右子数组的首位元素” 对应的索引;因此考虑使用二分法查找 “右子数组的首位元素"
算法解析:
1.初始化: 左边界 i = 0 ,右边界 j = len(nums) - 1;代表闭区间 [i, j]
2.循环二分: 当 i ≤ j 时循环
a.计算中点 m = (i + j) // 2m=(i+j)//2 ,其中 “” 为向下取整除法
b.若 nums[m] = m ,则 “右子数组的首位元素” 一定在闭区间 [m + 1, j ] 中,因此执行 i = m + 1
c.若 nums[m] !=m ,则 “左子数组的末位元素” 一定在闭区间 [i, m - 1] 中,因此执行 j = m - 1
3.返回值: 跳出时,变量 i 和 j 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 i 即可
def missingNumber(self, nums: List[int]) -> int:
i, j = 0, len(nums)-1
while i <= j:
m = (i+j)//2
if nums[m] == m: i = m + 1
else: j = m - 1
return i