Simple Python Solution with Swapping


  • 0

    If we find the (index of the element) + 1 is not equal to the element, just swap the element to the position (element -1). If the swapping enters any loop, just quit.
    At last, the element which is not consistent with the index is the answer.

    class Solution(object):
        def findDisappearedNumbers(self, nums):
            for i in range(len(nums)):
                while nums[i]!= i+1:
                    nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
                    if nums[nums[i]-1] == nums[i]:
                        break
            return [i+1 for i in range(len(nums)) if i+1 != nums[i]]

  • 0
    J

    If I follow your code correctly, is it bubble sort? If it is, I am surprised that it runs very fast, since bubble sort is O(n^2), but yeah, there are only around 10 numbers in the test cases..


  • 0

    Yes it is bubble sort......O(n^2)..
    A better solution is just sort and scan once to get the result. O(nlgn) + O(n)


  • 0
    C

    I don't think this is bubble sort... Bubble sort compares adjacent elements and moves an element to the correct position by making many swaps. This takes advantage of the fact that all the numbers are less than the length of the list by putting each element directly into the position that it belongs. Also, it doesn't sort the duplicate elements because of the 'if' statement. O(n)


Log in to reply
 

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