268. Missing Number

女爷i 2022-07-12 11:53 147阅读 0赞

# 268. Missing Number #

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

For example,  
Given nums = \[0, 1, 3\] return 2.

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

本题意思是说，已经有一串数字，0-n，然后有一个数字被拿掉了，请找到这个数字

## 第一种解法 ##

第一反应

就是这个实际上可以理解成，1-n这n个数字有一个被替换为0 （不包含n这个），所以解法就是1-n求和减去0-n求和，剩下的就是那个数字

func missingNumber(nums []int) int {
        nums_len := len(nums)
        sum := 0
    
        for i := 0; i < nums_len; i++ {
            sum += nums[i]    
        }
    
        answer_num := (1 + nums_len) * nums_len / 2 - sum
    
        return answer_num
    }

## 第二种解法 ##

基本上是第一种解法的变体，不过是利用位运算的特性

index跟数组index位置的值全部求异或，假设是i这个值不存在，那么最后的值就是0^i=i，也就求出来所需要寻找的数字

func missingNumber(nums []int) int {
        nums_len := len(nums)
        answer := nums_len
    
        for index := 0; index < nums_len; index++ {
            answer ^= index
            answer ^= nums[index]
        }
    
        return answer
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Easy - 268. Missing Number

Topic Array Math Bit Manipulation Description [https://leetcode.com/prob

小灰灰/ 2023年01月07日 08:46/ 0 赞/ 139 阅读

相关 [leetcode]268. Missing Number -- JavaScript 代码

/ @param {number[]} nums @return {number} / var missingNumber = function(nums)

雨点打透心脏的1/2处/ 2022年09月25日 06:20/ 0 赞/ 145 阅读

相关 268. Missing Number

268. Missing Number Given an array containing n distinct numbers taken from 0, 1, 2,

女爷i/ 2022年07月12日 11:53/ 0 赞/ 148 阅读

相关 268. Missing Number

268. Missing Number Given an array containing n distinct numbers taken from 0, 1, 2,

你的名字/ 2022年07月12日 11:53/ 0 赞/ 195 阅读

相关 [leetcode]: 268. Missing Number

1.题目 Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the

迈不过友情╰/ 2022年06月14日 23:20/ 0 赞/ 175 阅读

相关 268. Missing Number

/ 268. Missing Number Given an array containing n distinct numbers tak

╰半橙微兮°/ 2022年06月09日 03:55/ 0 赞/ 188 阅读

相关 LeetCode268. Missing Number解题

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

雨点打透心脏的1/2处/ 2022年06月05日 05:35/ 0 赞/ 195 阅读

相关 268. Missing Number

给出一个包含 `0, 1, 2, ..., n` 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。 / Created by Joe on 20

r囧r小猫/ 2022年05月26日 22:58/ 0 赞/ 183 阅读

相关 leetcode-268 Missing Number

题目找到缺少的数字 Given an array containing n distinct numbers taken from 0, 1, 2, …, n, fi

落日映苍穹つ/ 2022年03月09日 14:39/ 0 赞/ 236 阅读

相关 leetcode_268.missing number

给定一个数组nums，其中包含0--n中的n个数，找到数组中没有出现的那个数。解法一：cyclic swapping algorithm class Soluti

ゝ一纸荒年。/ 2021年12月24日 14:45/ 0 赞/ 231 阅读