首页 > 代码库 > 【LeetCode】Single Number
【LeetCode】Single Number
题目
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
思路:
为了满足时间和空间复杂度,必须利用异或的性质。
异或: 1 XOR 1 = 0 0 XOR 0 = 0 1 XOR 0 = 1 0 XOR 1 = 1 即相同为 0,不同为1
根据异或性质,有如下等式: 对任意整数,a b c , a XOR a = 0 a XOR b XOR a = b
即任意两个相同的数异或一定得 0, 若是一堆数,除了一个数,其他都是成对出现,则将所有数异或起来,剩下的就是我们要找的数。复杂度为 O(n)
代码:
class Solution{ public: int singleNumber(int A[], int n) { int ans; for(int i = 0; i < n;++i) ans ^= A[i]; return ans; } };
【LeetCode】Single Number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。