【Python3】【力扣题】268. 丢失的数字

【力扣题】题目描述：

【Python3】代码：

1、解题思路：哈希。元素去重，依次判断是否在0-n内，没有则返回。

知识点：set(...)：转为集合，集合中的元素不重复。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        a = set(nums)
        for i in range(len(nums)+1):
            if i not in a:
                return i

2、解题思路：集合的差。0-n的集合与元素去重后的集合的差，即没有出现的数字。

知识点：set(a)-set(b)：获取a中有但b中没有的元素。返回集合。

              集合.pop()：随机移除元素并返回该元素。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        aset = set(range(len(nums)+1)) - set(nums)
        return aset.pop()

3、解题思路：排序。下标与元素一致，若不一致，则下标对应的元素没有出现。若都一样，则n没有。

知识点：序列.sort()：在原序列基础上排序，改变原序列。

              enumerate(序列)：返回可迭代的下标和下标对应的元素，下标从0开始。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i,x in enumerate(nums):
            if i != x: 
                return i
        return len(nums)

4、解题思路：异或。将各元素和0-n都进行异或，最终结果为只出现一次的元素，即原列表没有的数字。

按位异或运算 ⊕满足交换律和结合律，且对任意整数 x都满足：x⊕x=0 和 x⊕0=x。

知识点：a ^ b：a和b异或。 

注解：两两异或，res记录异或的结果。

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

5、解题思路：数学。0-n的和为，与各元素和 相减，结果为没有出现的数字。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        return n*(n+1)//2 - sum(nums)