首页 > 代码库 > [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?
本来是一道非常简单的题,但是由于加上了时间复杂度必须是O(n),并且空间复杂度为O(1),使得不能用排序方法,也不能使用map数据结构。那么只能另辟蹊径,这个解法如果让我想,肯定想不出来,因为谁会想到用逻辑异或来解题呢。逻辑异或的真值表为:
异或运算的真值表如下:
A | B | ⊕ |
---|---|---|
F | F | F |
F | T | T |
T | F | T |
T | T | F |
由于数字在计算机是以二进制存储的,每位上都是0或1,如果我们把两个相同的数字异或,0与0异或是0,1与1异或也是0,那么我们会得到0。根据这个特点,我们把数组中所有的数字都异或起来,则每对相同的数字都会得0,然后最后剩下来的数字就是那个只有1次的数字。这个方法确实很赞,但是感觉一般人不会忘异或上想,绝对是为CS专业的同学设计的好题呀,赞一个~~
代码如下:
class Solution {public: int singleNumber(int A[], int n) { int res = A[0]; for (int i = 1; i < n; ++i) res ^= A[i]; return res; }};
[LeetCode] Single Number 单独的数字
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。