268. Missing Number（查找遗漏的数）

素颜马尾好姑娘i 2022-07-14 06:07 96阅读 0赞

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\]的n个不同的整数，因为\[0，n\]共有n+1个整数，找到遗漏的那个数。

解题思路：

解法一：\[0，n\]中这n+1个数的和为sum = 0+1+...+n = n \* (n + 1) / 2，用sum减去给定的n个数的和，得到的就是遗漏的那个数。代码如下：（1ms，beats 43.60%）

public class Solution {
        public int missingNumber(int[] nums) {
            int n = nums.length;
    		int sum = n * (n + 1) / 2;
    		for (int num : nums)
    			sum -= num;
    		return sum;
        }
    }

解法二：令int xor = 0，先用给定的n个数与之异或，再用\[0，n\]这n+1个数与之异或，最后的结果就是遗漏的那个数。因为相同的两个数异或结果为0，而一个数与0异或的结果为这个数本身。代码如下： （1ms，beats 43.60%）

public class Solution {
        public int missingNumber(int[] nums) {
            int xor = 0;
    		for(int num:nums)
    			xor ^= num;
    		int n = nums.length;
    		while(n>=0)
    			xor ^= n--;
    		return xor;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode 268. Missing Number

目录一、问题分析二、代码实现 1、数学运算 2、位运算 -------------------- [https://leetcode.com/proble

迷南。/ 2023年07月12日 05:05/ 0 赞/ 1 阅读

相关 LeetCode - Easy - 268. Missing Number

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

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

相关 268. Missing Number（查找遗漏的数）

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

素颜马尾好姑娘i/ 2022年07月14日 06:07/ 0 赞/ 97 阅读

相关 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 赞/ 149 阅读

相关 268. Missing Number

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

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

相关 [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 阅读

相关 268. Missing Number

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

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

相关 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 赞/ 232 阅读