教程建设网站软件网站开发评估

教程建设网站,软件网站开发评估,中文企业网站设计欣赏,常州做网站咨询题目介绍 给你一个 非空 整数数组 nums #xff0c;除了某个元素只出现一次以外#xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题#xff0c;且该算法只使用常量额外空间。 提示#xff1a; 1 …题目介绍给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。提示1 nums.length 3 * 104-3 * 104 nums[i] 3 * 104除了某个元素只出现一次以外其余每个元素均出现两次。class Solution { public: int singleNumber(vectorint nums) { } };全文1300字阅读思考 8min原题链接136. 只出现一次的数字 - 力扣LeetCode解析1 . 本题需求很简单即给你一个数组(vectorint) 找出数组中只出现一次的数字并返回且其余数字都出现了两次哈希1 . 对于要找出单身狗数字很容易想到的思路遍历数组一遍统计每个数字出现的次数2 . 只需要统计一遍就能知道每个数字出现多少遍。代码初步构建class Solution { public: int singleNumber(vectorint nums) { mapint,int mp;// 数字 出现的次数 for(auto e:nums) { mp[e]; } //统计完毕 } };3 . 已经统计好每个数字出现的次数那么再遍历一遍数组4 . 一旦遇到次数为1即mp[e] 1)就立刻返回eclass Solution { public: int singleNumber(vectorint nums) { mapint,int mp;// 数字 出现的次数 for(auto e:nums) { mp[e]; } for(auto e:nums) { if(mp[e] 1) return e; } return 0;//为了编译通过需要再加一个return } };注1 . 这个方法逻辑和写法没有问题2 . 可使用了O(n)的空间开销而非常量但时间开销符合要求O(n)异或此方法重点掌握——1 . 回忆异或。全称按位异或——二进制位运算之一2 . 异或的本质 模二乘法运算a . 0 ^ 0 0 0 ^ 1 1 1^1 0b . a ^ 0 a a ^ a 0;3 . 我们正是利用”b中式子”完成需求a . 当给出的数组都是成双成对的数字那么可想而知将所有数字进行异或结果为0b , 异或运算与顺序无关它只与参与运算的位有关c . 当数组中出现唯一一个单身狗数字那么 0 ^ singleDog singleDogd. 所以这个singleDog就是将所有数组异或之后的结果代码呼之欲出class Solution { public: int singleNumber(vectorint nums) { int sigledog 0;// 设置单身狗的初始值为0因为0和任何数异或都保持为该数 for(auto e:nums) { sigledog ^ e; } return sigledog; } };总结以及完整参考代码class Solution { public: int singleNumber(vectorint nums) { mapint,int mp;// 数字 出现的次数 for(auto e:nums) { mp[e]; } for(auto e:nums) { if(mp[e] 1) return e; } } };class Solution { public: int singleNumber(vectorint nums) { int sigledog 0;// 设置单身狗的初始值为0因为0和任何数异或都保持为该数 for(auto e:nums) { sigledog ^ e; } return sigledog; } };本周其他算法一见15 . 有效的括号-CSDN博客16 . 买卖股票的最佳时机-CSDN博客17 . 爬楼梯-CSDN博客18 . 杨辉三角-CSDN博客20 . 多数元素-CSDN博客赶快动起手来吧