LeetCode 268. Missing Number

简介: 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

v2-3b3518bd0fedf66479bd0f2bb0e5c92c_1440w.jpg

Description



Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.


Example 1:

Input: [3,0,1]

Output: 2


Example 2:

Input: [9,6,4,2,3,5,7,0,1]

Output: 8


Note:

Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?


描述



给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。


示例 1:

输入: [3,0,1]

输出: 2


示例 2:

输入: [9,6,4,2,3,5,7,0,1]

输出: 8

说明:

你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?


思路


1.异或运算



  • 亦或运算.
  • 由于亦或运算相同为0,不同为1,那么一个数字自己和自己做异或运算结果为0,即偶数个相同的数亦或为0,奇数个相同的数亦或为本身.
  • 给定的数从0到n一共n个数(丢失了一个),我们在加一个辅助变量i从0到n,让给定的所有数和0到n的所有数字做亦或运算,则相同的数两两配对亦或为0,丢失的数只会在i中出现了一次,于是会被保留.
  • 为了方便,我们让i从0到n-1,另res初始化为n,所以结果 res = nums[0] ^ nums[1] ... ^ nums[n-1] ^0 ^1 ^ ...^n,即 res ^= nums[0] ^nums[1] ... ^nums[n-1] ^0 1...n-1'


2.求和



  • 0到n的和为n*(n+1)/2,用这个和与原数组的和做差记为缺少的数字.


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-04 15:30:54
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-04 16:05:54
class Solution:
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return len(nums) * (len(nums) + 1) // 2 - sum(nums)
    def missingNumber2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 位运算  0^0^1^2^2^3^3^4^4 = 1
        # 即偶数次亦或结果为0,奇数次为本身
        # 给定的数范围从0到n共n个(丢失了一个),我们然i从0自增到n-1,另res初始化为n。
        # 对所有的数进行异或运算,重复出现的数字两两配对,抑或的结果为0
        # 落单的数字亦或会被保留
        res = len(nums)
        for i in range(len(nums)):
            res ^= i ^ nums[i]
        return res


源代码文件在这里.


目录
相关文章
|
11月前
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
92 1
|
4月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
5月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
39 0
|
11月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
36 0
|
C++ 容器
【PAT甲级 - C++题解】1144 The Missing Number
【PAT甲级 - C++题解】1144 The Missing Number
59 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
88 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
91 0
LeetCode 313. Super Ugly Number