彩世界平台-彩世界时时app-彩世界开奖app苹果下载

热门关键词: 彩世界平台,彩世界时时app,彩世界开奖app苹果下载

您的位置:彩世界平台 > 彩世界平台 > LeetCode.442. Find All Duplicates in an Array

LeetCode.442. Find All Duplicates in an Array

发布时间:2019-09-01 10:03编辑:彩世界平台浏览(168)

    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(n2),列表的方法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)找突破口,哎,还得好好努力啊。

     

     

    . Find All Duplicates in an Array, 问题描述如下: Given an array of integers, 1 ≤ a[i] ≤ n ( n = size of array), some elements appeartwiceand others appearon...

    问题描述如下:

    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(n2),列表的方法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
    

    本文由彩世界平台发布于彩世界平台,转载请注明出处:LeetCode.442. Find All Duplicates in an Array

    关键词:

上一篇:python Django 文件下载示例

下一篇:没有了