您好,欢迎来到二三娱乐。
搜索
您的当前位置:首页[LeetCode]442. Find All Duplicat

[LeetCode]442. Find All Duplicat

来源:二三娱乐
题目

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
难度

Medium

方法

因为1=<a[i]<=n,那么0<=a[i]-1<=n-1,因此可以将a[i]-1作为index。如果a[i]有2个,那么a[i]-1会出现2次。当a[i]第一次出现时,将a[a[i]-1]置为负值。将i++,如果a[a[i]-1]为负数的时候,表示a[i]之前一定出现过。
由于a[i]会被置为负数,因此a[a[i]-1]需要用a[abs(a[i])-1]

python代码
class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        duplicates = []
        for i in range(len(nums)):
            index = abs(nums[i])-1
            if nums[index] < 0:
                duplicates.append(index+1)
            else:
                nums[index] = -nums[index]

        return duplicates

assert Solution().findDuplicates([4,3,2,7,8,2,3,1]) == [2,3]
assert Solution().findDuplicates([10,2,5,10,9,1,1,4,3,7]) == [10,1]

Copyright © 2019- yule263.com 版权所有 湘ICP备2023023988号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务