Python, sort nums in O(n)


  • 0
    P
        def findDisappearedNumbers(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            n = len(nums)
            # sort it with O(n)
            for i in range(n):
                while i != nums[i] - 1 and nums[i] != nums[nums[i]-1]: 
                    next = nums[i]-1
                    nums[i], nums[next] = nums[next], nums[i]
    
            result = []
            for i, x in enumerate(nums):
                if i + 1 != x:
                    result.append(i+1)
            return result  
    

Log in to reply
 

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