題目:

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

給定一個陣列,裡面本來應該有0~n的數各一,找出缺少的那個數
ex:input:[3,0,1]=>output:2

這題的解法有好幾種
先從直觀的開始講好了

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        if 0 not in nums: #先確認missing number是不是0
            return 0
        
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i]+1 != nums[i+1]:
                return nums[i]+1
            
        return len(nums) #都沒找到不連續的點,代表missing number在尾端

先將陣列排序後再遍歷
一發現不連續的點,即代表發現missing number的位置
且記得考量到missing number在頭尾的可能
最後執行時間140ms(faster than 92.08%)

也有不用事先排序的解法

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        total=0
        for i in range(1,len(nums)+1):
            total=total+i
        return total-sum(nums)

只要算出0~n的總和,再減去陣列數的總和
結果就是我們要的missing number
最後執行時間128ms(faster than 98.93%)

接下來這個解法是在討論區看到的
我也沒想到這題居然能用位元運算下去解

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        xsum = 0
        for x in nums: 
            xsum ^= x
        
        for i in range(len(nums)+1):
            xsum ^= i
        
        return xsum

設一數0和nums每個數做^運算,再和0~n每個數做^運算,最後的結果就是missing number
至於為什麼,我們以[3,0,1]為例,操作起來如下
0^3^0^1^0^1^2^3經過交換律後變為
0^0^0^1^1^2^3^3又x^x=0
0^0^2^0=0^2=2,而2就是我們要的missing number
最後執行時間133ms(faster than 97.07%)

那我們下題見