LeetCode.442. Find All Duplicates in an Array

问题描述如下:

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]

我的第一个解法：时间超时：

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res=[]
        nums.sort()
        for i in nums:
            if nums.count(i)==2:
                res.append(i)
        #for j in res:
         #   res.remove(j)
        #return res
        res=res[::2]
        return res

我搞不清楚问题出在哪？难道是我的时间复杂度为O（n²），列表的方法count时间复杂度应该为O（n）,所以导致我的程序超时。

第二个解决方法：逻辑不对，不能给出正确输出。

 def findDuplicates(self, nums):  
        """ 
        :type nums: List[int] 
        :rtype: List[int] 
        """  
        #res=[]  
        nums.sort()  
        for i in nums:  
            if nums.count(i)==1:  
                nums.remove(i)  
        for j in nums:  
            nums.remove(j)  
        return nums

这个方法的问题在于remove这个函数，每遍历一次，序列便会移除第一个匹配的元素，这样会让原数组变化，遍历就会出问题，有的元素就会被忽略，从而导致最后的结果有错误。

方法二的改进版：时间超时，还是不行的。

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res=nums[:]
        res.sort()
        for i in nums:
            if nums.count(i)==1:
                res.remove(i)
        #for j in res:
         #   res.remove(j)
        #return res
        res=res[::2]
        return res

当然后来我尝试过加入一个空数组来存放数据，如上的代码。貌似也还是超时，就是说不能用count这个函数，因为时间复杂度很高。

正确的方法：

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

这个方法确实让人想不到，我想了好久，没想到，利用条件：1 ≤ a[i] ≤ n (n = size of array)，出现两次的数字必然在数组的长度范围之内，然后用这个数字做索引，数组里面也必然有对应的元素，把它改成负数，因为相同的数字减去1后（因为数组下标从0开始，需要减1，因为1 ≤ a[i] ≤ n (n = size of array)，减1之后做索引肯定可以索引到数组的元素，也就是有一个参照物了）所对应的索引是一样的，数字出现第一次之后，减去1后对应的索引对应的数字，取负数之后，当数字第二次出现时，取到这个负数之后，满足判断条件，那么就会确定这个数字出现两次了。当然那些只出现一次的数字，只会把索引对应的值变为负数，也有可能把那些出现两次的数字其中的一个对应的索引值变成负数。

总结：这题真是让我很难想到这种方法，好难想的，应该从条件：1 ≤ a[i] ≤ n (n = size of array)找突破口，哎，还得好好努力啊。

python学习网

分类

LeetCode.442. Find All Duplicates in an Array