潍坊寿光网站建设,php做网站需要的技术,网站建设公众号管理,网站运营方案模板题目解析
268. 丢失的数字 本题的意思就是数组的长度为n#xff0c;在[0,n]区间中寻找缺失的一个数字 算法讲解
直观思路#xff1a;排序 Hash#xff0c;顺序查找缺失的数字
优化#xff1a;使用异或#xff0c;首先将[0,n]之间所有数字异或在一起#xff0c;然后将…题目解析
268. 丢失的数字 本题的意思就是数组的长度为n在[0,n]区间中寻找缺失的一个数字 算法讲解
直观思路排序 Hash顺序查找缺失的数字
优化使用异或首先将[0,n]之间所有数字异或在一起然后将顺序异或nums数组中的每一个元素最后异或完成之后就是那个缺失的数字
class Solution {
public:int missingNumber(vectorint nums) {int n nums.size();int ret 0;for(int i 0; i n; i){ret ^ i;}//寻找缺失的数字for(int i 0; i n; i){ret ^ nums[i];}return ret;}
};按照上面的代码比如当前在[0,4]区间中寻找确实的数字首先将ret 0 ^ 1 ^ 2 ^ 3 ^ 4 ; 之后再让ret ret ^ 0 ^ 1 ^ 3 ^ 4; 得到ret 2;
