O(n) time, O(1) space Python solution with explaination


  • 0
    X

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

    sort, get [1,2,2,3,3,4,7,8]

    then the solution takes two rounds of n elements, for the first round, we'll put every elements we met into place it belongs. For those numbers who is not in the expected position, we'll use -1 to hold the place. Along with 'i' increasing, some of the -1s will be replaced by this line: nums[nums[i] - 1] = nums[i]. So at the end of the first round, those who disappeared will keep -1s.

    second round to collect the placeholders

    class Solution(object):
        def findDisappearedNumbers(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            if len(nums) < 2:
                return []
            nums.sort()    #[1,2,2,3,3,4,7,8]
            result = []
            for i in range(len(nums)):
                #find the position of nums[i] #
                nums[nums[i] - 1] = nums[i] 
                if nums[i] != i + 1:
                    nums[i] = -1
    
            #now the nums looks like [1,2,3,4,-1,-1,7,8]
    
            for j in range(len(nums)):
                if nums[j] == -1:
                    result.append(j + 1)
            return result
    

  • 0
    S

    Sorting itself is O(nlogn), so your solution is not O(n) in time.


  • 0
    X

    That's true, thanks for pointing out! How about this, without sorting, I'll just go as far as I could to re-arrange the numbers for each 'i'.

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

    [-1,3,2,4,8,2,3,1] temp = 7

    [-1,3,2,4,8,2,7,1] temp = 3

    ...

    [-1,2,3,4,8,2,7,1] after first while loop

    ...

    [1,2,3,4,-1,-1,7,8]

    then get result based on -1s

    class Solution(object):
        def findDisappearedNumbers(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            if len(nums) < 2:
                return []
            result = []
            for i in range(len(nums)):
                if nums[i] != i + 1:
                    temp = nums[i]
                    nums[i] = -1
                    while nums[temp - 1] != temp and temp != -1:
                        t = nums[temp - 1]
                        nums[temp - 1] = temp
                        temp = t
                        
            for j in range(len(nums)):
                if nums[j] == -1:
                    result.append(j + 1)
            return result
    

  • 0
    R

    @samk522 we can use O(n) sort for this case since elements are from 1 to n


Log in to reply
 

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