跳转至

LeetCode: 442. 数组中重复的数据

1、题目描述

给定一个整数数组 a,其中1 ≤ a[i] ≤ nn*为数组长度), 其中有些元素出现**两次**而其他元素出现**一次*

找到所有出现**两次**的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

2、解题思路

​ 这道题与448题基本一致,区别就在于一个找重复的,一个找消失的,思路都是一样的

  • 首先,遇到一个元素k,我们就判断这个元素对应的下标a[k-1]是不是负数,如果是,加入结果数组中,并将这个元素变成正数
  • 遍历到头即可
class Solution:
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = []
        for i in nums:
            i = abs(i)
            if nums[i - 1] < 0:
                ans.append(i)

            nums[i-1] = -nums[i-1]

        return ans

​ 只要理清思路,就会变得非常简单。