网站如何防采集,高校门户网站建设需要多少钱,wordpress主题模板源码,建盏名家罗建明简介268. 丢失的数字
难度#xff1a;简单
题目
给定一个包含 [0, n] 中 n 个数的数组 nums #xff0c;找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1#xff1a;
输入#xff1a;nums [3,0,1]
输出#xff1a;2
解释#xff1a;n 3#xff0c;因为有 3…268. 丢失的数字
难度简单
题目
给定一个包含 [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 [9,6,4,2,3,5,7,0,1]
输出8
解释n 9因为有 9 个数字所以所有的数字都在范围 [0,9] 内。8 是丢失的数字因为它没有出现在 nums 中。示例 4
输入nums [0]
输出1
解释n 1因为有 1 个数字所以所有的数字都在范围 [0,1] 内。1 是丢失的数字因为它没有出现在 nums 中。提示
n nums.length1 n 10^40 nums[i] nnums 中的所有数字都 独一无二
进阶你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
个人题解
方法一异或运算
异或性质
0 ^ n n
n ^ n 0
思路
由题独一无二可知利用异或运算的性质即可求出这里面没有的数即定义一个变量初始为0将 0~n 的所有数与该变量异或然后再与数组中所有数异或最后的结果便是丢失的数字
class Solution {public int missingNumber(int[] nums) {int result 0;for (int i 0; i nums.length; i) {result ^ i;result ^ nums[i];}result ^ nums.length;return result;}
}复杂度分析
时间复杂度O(n)空间复杂度O(1)
官方题解
方法一排序
class Solution {public int missingNumber(int[] nums) {Arrays.sort(nums);int n nums.length;for (int i 0; i n; i) {if (nums[i] ! i) {return i;}}return n;}
}复杂度分析
时间复杂度O(n logn)空间复杂度O(1)
方法二哈希集合
首先遍历数组 nums 将数组中的每个元素加入哈希集合然后依次检查从 0 到 n 的每个整数是否在哈希集合中不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 O(1) 因此总时间复杂度是 O(n)
class Solution {public int missingNumber(int[] nums) {SetInteger set new HashSetInteger();int n nums.length;for (int i 0; i n; i) {set.add(nums[i]);}int missing -1;for (int i 0; i n; i) {if (!set.contains(i)) {missing i;break;}}return missing;}
}复杂度分析
时间复杂度O(n)空间复杂度O(n)
方法三位运算
class Solution {public int missingNumber(int[] nums) {int xor 0;int n nums.length;for (int i 0; i n; i) {xor ^ nums[i];}for (int i 0; i n; i) {xor ^ i;}return xor;}
}复杂度分析
时间复杂度O(n)空间复杂度O(1)
方法四数学
将从 0 到 n 的全部整数之和记为 total根据高斯求和公式 total (n * (n1)) / 2
将数组 nums 的元素之和记为 arrSum则 arrSum 比 total 少了丢失的一个数字因此丢失的数字即为 total 于 arrSum 之差。
class Solution {public int missingNumber(int[] nums) {int n nums.length;int total n * (n 1) / 2;int arrSum 0;for (int i 0; i n; i) {arrSum nums[i];}return total - arrSum;}
}复杂度分析
时间复杂度O(n)空间复杂度O(1)
作者力扣官方题解 链接https://leetcode.cn/problems/missing-number/solutions/1085105/diu-shi-de-shu-zi-by-leetcode-solution-naow/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
