Leetcode268 缺失数字

/ 0评 / 0

题目描述

file

我的:字典解法

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        flag = dict()
        for num in nums:
            flag[num] = 1
        for num in range(n+1):
            if num not in flag:
                return num

 

数学解法

思路就是高斯求和公式先求出[0,1,···,n]的和,再减去数组中所有数字的和,就是缺失的数字。

class Solution:
    def missingNumber(self, nums):
        expected_sum = len(nums)*(len(nums)+1)//2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

 

位运算解法

file

class Solution:
    def missingNumber(self, nums):
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing

 

Note

发表评论

电子邮件地址不会被公开。