首页 > 代码库 > [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?
Solution:
XOR
Information about XOR:
异或运算的几个相关公式：
1. a ^ a = 0
2. a ^ b = b ^ a
3. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
4. d = a ^ b ^ c 可以推出 a = d ^ b ^ c
5. a ^ b ^ a = b
本题可以抽象成：int数组里有x1, x2 ... xn（每个出现2次），和y（只出现一次），得出y的值。
由公式2可知，数组里面所有数异或的结果等于 x1^x1^x2^x2^...^xn^xn^y
由公式3可知，上式等于(x1^x1)^(x2^x2)^...^(xn^xn)^y
由公式1可知，上式等于(0)^(0)^...(0)^y = y
因此只需要将所有数字异或，就可得到结果。
1 public class Solution {2 public int singleNumber(int[] A) {3 int result = 0;4 for(int i=0;i<A.length;++i){5 result^=A[i];6 }7 return result;8 }9 }
[Leetcode] Single Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。