( 位运算 ) 268. 丢失的数字 ——【Leetcode每日一题】
❓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.length
- 1 < = n < = 1 0 4 1 <= n <= 10^4 1<=n<=104
- 0 <= nums[i] <= n
nums
中的所有数字都 独一无二
进阶: 你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
💡思路:
基础知识必知:位运算基本原理
仅用线性复杂度和额外常数空间,基本上就是使用位运算了!
两个相同的数异或的结果为 0
:
- 对所有数以及数组下标
[0, n]
进行异或操作,最后的结果就是单独出现的那个数。
🍁代码:(Java、C++)
Java
class Solution {
public int missingNumber(int[] nums) {
int ans = 0;
for(int i = 0; i < nums.length; i++){
ans = ans ^ (i + 1) ^ nums[i];
}
return ans;
}
}
C++
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ans = 0;
for(int i = 0; i < nums.size(); i++){
ans = ans ^ (i + 1) ^ nums[i];
}
return ans;
}
};
🚀 运行结果:
🕔 复杂度分析:
- 时间复杂度:
O
(
n
)
O(n)
O(n),其中
n
为数组的长度。 - 空间复杂度: O ( 1 ) O(1) O(1)。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!