Python 4 lines with short explanation


  • 33

    For each number i in nums,
    we mark the number that i points as negative.
    Then we filter the list, get all the indexes
    who points to a positive number.
    Since those indexes are not visited.

    class Solution(object):
        def findDisappearedNumbers(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            # For each number i in nums,
            # we mark the number that i points as negative.
            # Then we filter the list, get all the indexes
            # who points to a positive number
            for i in xrange(len(nums)):
                index = abs(nums[i]) - 1
                nums[index] = - abs(nums[index])
    
            return [i + 1 for i in range(len(nums)) if nums[i] > 0]
    
    

  • 8
    T

    Thanks for the insight. A very minor improvement to get rid of the minus one plus one consideration.

    def findDisappearedNumbers(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            nums = [0] + nums
            for i in range(len(nums)):
                index = abs(nums[i])
                nums[index] = -abs(nums[index])
            
            return [i for i in range(len(nums)) if nums[i] > 0]
    

  • 0
    R

    @yang2007chun Hello,can you explain why two numbers that are duplicates allow for the index to be negative? Since, the value which is already negative will be multiplied by negative to become positive.


  • 0

    @rahul172 Hi,
    I think there is some misunderstanding. There does not seem to have multiplication in the code ( am I missing something? ). The code here simply make sure the visited value is negative inspect of whether the value was negative or positive before the operation:

       nums[index] = - abs(nums[index])
    

    As you can see, the '- abs' makes sure value is negative..
    Does that clear the confusion?


  • 1
    A

    Great solution for satisfying O(n) and no extra space.
    This solution is really slow for some reason though: 479 ms when the distribution of answers is somewhere between 25-110ms.


  • 0
    W

    Thank you! A great solution!


  • 3
    M

    This is more Pythonic :D

    def findDisappearedNumbers(self, nums):
        for num in nums:
            index = abs(num) - 1
            nums[index] = -abs(nums[index])
                
        return [i + 1 for i, num in enumerate(nums) if num > 0]
    

  • 0
    M
    This post is deleted!

  • 0
    M
    This post is deleted!

  • -1
    S

    I think this solution would have faster runtime. I am able to run it on my computer, but I get an error of

    '''ValueError: min() arg is an empty sequence'''

    Anyone know why?

    Here is my code:

    '''class Solution(object):
    def findDisappearedNumbers(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    l = set([i for i in range(min(nums), max(nums)+1)])
    answer = l - set(nums)
    return list(answer)'''
    '''


  • -1
    D

    @yang2007chun
    return list(set([i for i in xrange(1,len(nums)+1)])-set(nums))


  • 0
    This post is deleted!

  • 2

    @yang2007chun LeetCode uses Python 2 and we were asked to "do it without extra space", so better use xrange instead of range.


  • 0

    @StefanPochmann Thank you!


  • 0
    G

    @yang2007chun you solution is great,and this is mine:

    class Solution(object):
        def findDisappearedNumbers(self, nums):
            return list(set(range(1,len(nums)+1))-set(nums)&set(range(1,len(nums)+1)))
    

  • 0
    Z

    here is my code, similarly to @Gene20

    class Solution:
        def findDisappearedNumbers(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            return list(set(range(1, len(nums)+1)).difference(set(nums)))
    

  • 0
    C

    @yang2007chun Great explanation. Thank you


  • 0
    V

    @yang2007chun So clever! How could you find out this solution :D


  • 0
    M

    Great and simple solution!!


  • 0
    N

    Firstly, thank you for genius answer to this question.
    Here is almost the same code, with one tweak, I used enumerate, where you can set start index, which (potentially) makes it cleaner and nicer.

    class Solution(object):
        def findDisappearedNumbers(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            for i in xrange(len(nums)):
                index = abs(nums[i])-1
                nums[index] = -abs(nums[index])            
                
            return [index for index, n in enumerate(nums, start=1) if n > 0]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.