本文最后更新于:2022年4月9日 中午
给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?
示例:
| 输入: [4,3,2,7,8,2,3,1]
输出: [2,3]
|
Solution
题解思路与 448
相似,
- 遍历数组的每个元素
- 把
|nums[i]|-1
索引位置的元素标记为负数,即 nums[|nums[i]|-1]*-1
- 当发现
nums[|nums[i]|-1]
已经为负数时,说明 |nums[i]|-1
已经出现过,即 nums[i]
出现重复。
| class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: res = [] for i in range(len(nums)): new_index = abs(nums[i]) - 1 if nums[new_index] > 0: nums[new_index] = nums[new_index] * -1 else: res.append(abs(nums[i])) return res
|
@xiao-xue-66
通过索引号排序,比如数字4
放到索引3
的位置,最后找排序后数组,与索引号没有相差1
便是重复元素。
| class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: res = [] for i in range(len(nums)): while nums[nums[i]-1] != nums[i]: nums[nums[i] - 1],nums[i] = nums[i], nums[nums[i] - 1] for i in range(len(nums)): if nums[i] != i+1: res.append(nums[i]) return res
|