怎么做链接网站,短网址赚钱平台,全网品牌推广,网络培训网站开发文献综述题目链接#xff1a; https://leetcode.cn/problems/missing-number/ 视频题解#xff1a; https://www.bilibili.com/video/BV1HS42197Hc/ LeetCode 268.丢失的数字
题目描述
给定一个包含 [0, n] 中 n 个数的数组 nums #xff0c;找出 [0, n] 这个范围内没有出现在数组… 题目链接 https://leetcode.cn/problems/missing-number/ 视频题解 https://www.bilibili.com/video/BV1HS42197Hc/ LeetCode 268.丢失的数字
题目描述
给定一个包含 [0, n] 中 n 个数的数组 nums 找出 [0, n] 这个范围内没有出现在数组中的那个数。
举个例子
输入nums [3,0,1]
输出2
解释n 3因为有 3 个数字所以所有的数字都在范围 [0,3] 内。2 是丢失的数字因为它没有出现在 nums 中。视频题解
丢失的数字
思路来源
思路来源
思路解析
方法一 位运算
首先来看一下异或运算的特点11转成二进制101113转成二进制1101它们之间的异或运算如下图 11 ^ 13 611 ^ 11 0可以看出对于二进制相同的bit位按位异或值是0比如1 ^ 1 00 ^ 0 0。不同值bit位按位异或值是1比如1 ^ 0 1。
利用异或运算符这个特性我们可以轻松解决这个题目。
对区间[0, n]和数组nums中所有的元素做异或运算在nums中的元素会出现两次不在nums中的元素只会出现一次两个相同的元素做异或值为0最后的结果就是不在nums中的元素。
比如n 3nums [3, 0, 1]。0 ^ 1 ^ 2 ^ 3 ^ 3 ^ 0 ^ 1 (0 ^ 0) ^ (1 ^ 1) ^ (3 ^ 3) ^ 2 0 ^ 2 2。最终2就是不在nums中的数字。
C代码
class Solution {
public:int missingNumber(vectorint nums) {int nums_len nums.size();int res nums_len;for (int i 0; i nums_len; i) {//[0,n]和nums中的元素做异或操作res ^ (i ^ nums[i]); }return res;}
};java代码
class Solution {public int missingNumber(int[] nums) {int nums_len nums.length;int res nums_len;for (int i 0; i nums_len; i) {//[0,n]和nums中的元素做异或操作res ^ (i ^ nums[i]);}return res;}
}python 代码
class Solution:def missingNumber(self, nums: List[int]) - int:nums_len len(nums)res nums_lenfor i in range(nums_len):#[0,n]和nums中的元素做异或操作res ^ (i ^ nums[i])return res方法二 数学运算
因为区间[0, n]上有n 1个元素数组nums中只有n个元素假设缺失的元素为X我们可以得到如下公式
0 1 ... n nums[0] nums[1] ... nums[n-1] X 我们只需要用区间[0, n]所有元素的和减去nums中所有元素的和就得到最终的结果X。
C代码
class Solution {
public:int missingNumber(vectorint nums) {int nums_len nums.size();int res nums_len;for (int i 0; i nums_len; i) {//[0,n]的和减去nums中所有元素的和res (i - nums[i]); }return res;}
};java代码
class Solution {public int missingNumber(int[] nums) {int nums_len nums.length;int res nums_len;for (int i 0; i nums_len; i) {//[0,n]的和减去nums中所有元素的和res (i - nums[i]);}return res;}
}python代码
class Solution:def missingNumber(self, nums: List[int]) - int:nums_len len(nums)res nums_lenfor i in range(nums_len):#[0,n]的和减去nums中所有元素的和res (i - nums[i])return res复杂度分析
时间复杂度 两种方法的整个过程都是只遍历了一遍数组所以时间复杂度为O(n)n为数组nums的长度。
空间复杂度 两种方法都只使用了几个整型变量所以空间复杂度都是O(1)。
