LeetCode442数组中重复的数据

发表于 | 更新于 | 分类于 |

题目描述

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

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

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

示例：

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

输出:
[2,3]

解题思路

思路一

是使用额外空间的一种方法，使用一个与数组 a 同大小的额外数组，来保存元素出现的次数。

初始化数组元素都为0，先遍历数组 a ，对遍历到的每个元素，将新数组中对应index的位置的元素值加一，最后遍历记录数组，如果数组中的数字为2，则将当前的index加入到结果中。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findDuplicates(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    l = len(nums) + 1
    result = []
    arr = [0] * l
    for i in nums:
        arr[i] = arr[i] + 1

    for index, j in enumerate(arr):
        if j == 2:
            result.append(index)
    return result

思路二

方法一中，使用了额外的空间，并不符合题目的要求。不过如果想要不使用额外空间，那就需要在原空间上面做文章了。

也是遍历原数组，取得每个数组的值的绝对值（因为后面有取负操作）并减一（索引是否从0开始的问题），操作对应的位置的值，如果是正数的话，取负号；如果是负数的话，说明之前已经被设过了，则表示已经出现过，将对应的元素添加到结果中。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findDuplicates(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    result = []
    for i in nums:
        index = abs(i) - 1
        if nums[index] > 0:
            nums[index] = -nums[index]
        else:
            result.append(abs(index+1))

    return result