442. 数组中重复的数据
给你一个长度为 n
的整数数组 nums
,其中 nums
的所有整数都在范围 [1, n]
内,且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数,并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n)
且仅使用常量额外空间的算法解决此问题。
示例 1:
输入:nums = [4,3,2,7,8,2,3,1]
输出:[2,3]
示例 2:
输入:nums = [1,1,2]
输出:[1]
示例 3:
输入:nums = [1]
输出:[]
提示:
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
nums
中的每个元素出现 一次 或 两次
- 注意到 n u m s nums nums范围在 [ 1 , n ] [1,n] [1,n]
- 将 n u m s [ i ] nums[i] nums[i]移动到 n u m s [ i ] − 1 nums[i]-1 nums[i]−1下,然后统计位置和值不匹配的项
注意::
- python中交换的顺序问题,若 n u m s [ i ] nums[i] nums[i]的值先改变, n u m s [ n u m s [ i ] − 1 ] nums[nums[i]-1] nums[nums[i]−1]的值则会发生错误
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
while nums[i] != nums[nums[i]-1]:
nums[nums[i]-1],nums[i] = nums[i],nums[nums[i]-1]
# nums[i],nums[nums[i]-1] = nums[nums[i]-1],nums[i]
return [n for i,n in enumerate(nums) if n-1!=i]
复杂度
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
- 因为最多出现两次,且 n ∈ [ 1 , 1 0 5 ] n\in [1,10^5] n∈[1,105],若 n n n出现,则将 n u m s [ n − 1 ] nums[n-1] nums[n−1]标记为负数
- 若当前访问的值已经被标记过了,则说明出现两次
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
res = []
for i in range(len(nums)):
pos = abs(nums[i])-1
if nums[pos]>0: nums[pos] = -nums[pos]
else: res.append(pos+1)
return res
复杂度
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)