268. Missing Number

Steven 发布于2019-07-30 17:01 / 2741人阅读

摘要：之后我们可以查看头尾两个数字是否符合要求。如果不符合我们可以直接返回结果。方法利用的特点。方法求和根据高斯定理，从到的和为。所以把数组的所有数字求和，然后与从到的和相减所得数字，就是我们需要的数字。

题目链接：Missing Number

思路：
方法1: 排序
我们很自然的可以想到，如果数组是排好序的，那么可以很容易的找到缺少的数字。
之后我们可以查看头尾两个数字是否符合要求。如果不符合我们可以直接返回结果。
最后，我们查从1到n-1个数字。

方法2: Bit Manipulation
利用“XOR”的特点。比如 1 XOR 1 = 0，但1 XOR 1 XOR 2 = 2。
所以只要把数组中的数字和数组中的index全部XOR，那么缺少的那个肯定是我们需要的数字。

方法3: HashSet
放数组的数字放到HashSet里面，然后遍历这个HashSet。如果数字不在就说明这是我们要找的数字。

方法4: 求和
根据高斯定理，从1到n的和为 ((1+n) * n)/2。
所以把数组的所有数字求和，然后与从1到n的和相减所得数字，就是我们需要的数字。

时间复杂度：
方法1:

时间：O(nlogn) 
空间：O(1) if we sort the numbers in place

方法2:

时间：O(n)
空间：O(1)

方法3:

时间：O(n)
空间：O(n)

方法4:

时间：O(n)
空间：O(1)

代码：

方法1：

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        if nums[0] != 0:
            return 0
        if nums[-1] != len(nums):
            return len(nums)
        
        for i in range(1, len(nums)):
            exp_val = nums[i-1] + 1
            if nums[i] != exp_val:
                return exp_val

方法2:

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = len(nums)
        for i, num in enumerate(nums):
            res ^= i ^ num
        return res

方法3:

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        n = len(nums) + 1
        for i in range(n):
            if i not in nums:
                return i

方法4:

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        exp_sum = len(nums) * (len(nums) + 1) // 2
        sum_n = sum(nums)
        return exp_sum - sum_n

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41961.html

268. Missing Number

摘要：题目解答一开始我的思始很简单，排序，查找但是可以用的方法，因为只有一个，所以可以把其它所有的数都配好对，剩下这个就是我们要找的这里很喔，因为只少了一个数，举个例子所以当我们把这些数的时候，唯一一个剩下的就是的这个数题目：Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the o...

NSFish 2019-08-14 14:18 评论0 收藏0
leetcode 268 Missing Number

摘要：题目详情题目的意思是输入一个长度为的数组，找到这个数字中不存在于数组中的丢失的数字思路我的想法是，用这个数的和减去数组中的每一个元素的值，最后剩下的值就是丢失的数字解法题目详情 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing fr...

tianyu 2019-08-15 13:54 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
LeetCode偶尔一题 —— 268. 缺失数字

摘要：题目描述给定一个包含中个数的序列，找出中没有出现在序列中的那个数。示例输入输出示例输入输出最简单的解法刚看到的这道题的时候，第一感觉就是排序，之后直接挨个比较就能找到缺失的数字。题目描述给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。示例 1: 输入: [3,0,1] 输出: 2 示例 2: 输入: [9,6,...

e10101 2019-08-26 10:22 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0