杭州微信网站开发漯河企业网站建设

杭州微信网站开发,漯河企业网站建设,wordpress首页显示全部内容,甘肃省建设厅质量投诉网站题目#xff1a;给你一个 非空 整数数组 nums #xff0c;除了某个元素只出现一次以外#xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题#xff0c;且该算法只使用常量额外空间。题解#xff1a;我觉着…题目给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。题解我觉着这是很有意思的一道题该问题看似简单但在时间和空间复杂度限制下非常考察对位运算的理解。一、最直观的思路为什么不选1使用哈希表统计次数最容易想到的方式是使用哈希表记录每个数字出现的次数再遍历哈希表找出次数为 1 的元素问题需要额外的存储空间空间复杂度为O(n)而本题的隐含要求是使用常量额外空间2 排序后相邻比较另一种思路是对数组排序成对比较相邻元素问题排序时间复杂度至少为O(n log n)不满足最优解要求二、最优解的核心思想异或运算1什么是异或XOR异或运算有几个非常重要的性质相同的数异或为 0a ^ a 0任何数与 0 异或仍是它本身a ^ 0 a异或满足交换律和结合律a ^ b ^ a b2这些性质意味着什么在数组中每个出现两次的数字x ^ x 0所有成对的数字最终都会“抵消”为 0剩下的唯一一个数0 ^ single single只出现一次的数字一定会被保留下来三、算法思路核心逻辑初始化一个变量res 0遍历数组中每一个元素将当前元素与res进行异或运算遍历结束后res就是只出现一次的数字整个过程不需要额外的数据结构只做一次遍历完全利用位运算完成四、总结本题的关键不在于遍历而在于如何“消掉”重复元素异或运算天然适合处理成对出现只剩一个不同值这是位运算在算法题中的经典应用一句话总结利用异或“相同为零、不同保留”的特性让所有成对数字互相抵消最终剩下的就是答案。class Solution { public: int singleNumber(vectorint nums) { int ans 0; for (int x : nums) { ans ^ x; } return ans; } };