Python O(N) time and without extra space


  • 0
    A
    class Solution(object):
    def missingNumber(self, nums):
        size = len(nums)
        for i in xrange(size):
            if nums[i] == i:
                continue
            while True:
                val = nums[i]
                if val == i or val == size:
                    break
                nums[val], nums[i] = nums[i], nums[val]
        
        for i in xrange(size):
            if nums[i] != i:
                return i
        return size
    

    Also, you can use bit operation on this question.

    class Solution(object):
    def missingNumber(self, nums):
        size = len(nums)
        val = 0
        for i in xrange(size+1):
            val ^= i
        
        for n in nums:
            val ^= n
        
        return val

Log in to reply
 

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