动漫网站logo,企业网站的步骤,广西seo公司,西双版纳傣族自治州天气预报15天个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【Leetcode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【Leetcode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述
给定一个包含 [0, n] 中 n 个数的数组 nums 找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例1 输入nums [3,0,1] 输出2 解释n 3因为有 3 个数字所以所有的数字都在范围 [0,3] 内。2 是丢失的数字因为它没有出现在 nums 中。 示例2 输入nums [0,1] 输出2 解释n 2因为有 2 个数字所以所有的数字都在范围 [0,2] 内。2 是丢失的数字因为它没有出现在 nums 中。 示例3 输入nums [0,1] 输出2 解释n 2因为有 2 个数字所以所有的数字都在范围 [0,2] 内。2 是丢失的数字因为它没有出现在 nums 中。 示例4 输入nums [0] 输出1 解释n 1因为有 1 个数字所以所有的数字都在范围 [0,1] 内。1 是丢失的数字因为它没有出现在 nums 中。 注意
n nums.length1 n 1040 nums[i] nnums 中的所有数字都 独一无二
2️⃣题目解析
总共有三种解法哈希、位运算、高斯求和。
这里只对位运算和高斯求和进行解释。
位运算求解原理
相同数组进行异或结果为00 ^ num num
高斯求和原理
把[0,n]的和记为sum1把数组nums中所有的元素之和记为sum2丢失的数字即为sum1 - sum2
3️⃣解题代码
解法1高斯求和
class Solution {
public:int missingNumber(vectorint nums) {int n nums.size(),sum1 0,sum2 0;for(int i 0;i n;i) sum1 nums[i];for(int i 0;i n;i) sum2 i;return sum2 - sum1; }
};解法2位运算
class Solution {
public:int missingNumber(vectorint nums) {int n nums.size(),ret 0;for(auto x : nums) ret ^ x;for(int i 0;i n;i) ret ^ i;return ret;}
};
