leetcode448--Find All Numbers Disappeared in an Array

leetcode448--Find All Numbers Disappeared in an Array

题目

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

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]


解答方法有很多种

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        ret = []
        ret[:] = nums
        
        for x in nums:
            ret[x-1]=0
        
        result = []
        for i in range(len(nums)):
            if ret[i]>0:
                result.append(i+1)
                
        return result

即出现了的就标记为0,不过这样新申请了空间,而且用了两个for,虽然也是O(n).

或者用计数也是和上面的想法基本上一样

还有一种方法,是利用之前找重复的数字方法,不过这次找到重复的就不管了,最后为正的一定是没有出现过的了

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        for x in nums:
            if nums[abs(x)-1] < 0:
                continue
            else:
                nums[abs(x)-1] *= -1
                
        ret = []
                
        for i in range(len(nums)):
            if nums[i]>0:
                ret.append(i+1)
                
        return ret
                
                


打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦