简洁大气的网站推荐,wordpress4.7.5下载,阿里巴巴网站建设哪家好,网页设计流程顺序文章目录 Tag题目来源题目解读解题思路方法一#xff1a;位运算 其他语言Cpython3 写在最后 Tag
【位运算-异或和】【数组】【2023-10-14】 题目来源
136. 只出现一次的数字 题目解读
给你一个数组#xff0c;找出数组中只出现一次的元素。题目保证仅有一个元素出现一次位运算 其他语言Cpython3 写在最后 Tag
【位运算-异或和】【数组】【2023-10-14】 题目来源
136. 只出现一次的数字 题目解读
给你一个数组找出数组中只出现一次的元素。题目保证仅有一个元素出现一次其余的元素都是出现两次的。
要求解题方法的时间复杂度为线性的空间复杂度为常数级别。 解题思路
如果不考虑时间复杂度与空间复杂度本题有多种解决方法比如哈希表记录每个元素出现的次数比如使用集合记录元素如果遇到第二次个元素则从集合中移除遍历到的元素最后集合中剩余的就是仅出现一次的元素。还有一种方法就是将数组中的元素全部放入集合中利用集合来去重集合中的数都是出现过一次的数现在将集合中元素和的二倍减去数组中元素和得到的结果就是数组中仅出现一次的元素。
本题的最优解法是位运算的方法。
方法一位运算
本题利用的是位运算的异或和知识我们知道
两个相同的数的异或和为 0任何数与 0 异或结果不变异或操作具有交换性。
利用以上异或和的三条性质我们可以这样解决本题
维护一个结果变量 res初始值为 0遍历数组中的所有元素与 0 进行异或操作相同元素之间的异或和为 0最后只剩下 0 数组中的出现过一次的数异或得到的就是数组中的出现过一次的数返回 res。
实现代码
class Solution {
public:int singleNumber(vectorint nums) {int res 0;for (int num : nums) {res ^ num;}return res;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为数组 nums 的长度。
空间复杂度 O ( 1 ) O(1) O(1)。 其他语言
C
int singleNumber(int* nums, int numsSize){int res 0;for (int i 0; i numsSize; i) {res ^ nums[i];}return res;
}python3
class Solution:def singleNumber(self, nums: List[int]) - int:ret 0for i in nums:ret ^ ireturn ret写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
