leetcode with python:268. Missing Number

题目:

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%)

那我们下题见