【Leetcode】#136 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?

题目大意是给出一个int整型数组,其中每个元素都出现了两次,唯独有一个元素只出现了一次,请找出这个元素?要求时间复杂度为O(n),空间复杂度为O(1)。

对O(n)的时间复杂度要求,限制了解题自由。看了Discuss的答案,是使用位操作的逻辑异或来解题的。

逻辑异或的相关概念:
(1)基本运算:

1^1 = 0
0^0 = 0
1^0 = 1
0^1 = 1

(2)满足交换律:

a^b = b^a 

(3)与0求异或等于它本身;自身异或等于0:

a^0 = a
a^a = 0

这样,我们的思路就明确了,既然异或运算符合交换律、自身异或等于0、与0异或等于它本身,那么将所有的元素求异或,即可求得只出现一次的那个元素。同时,只对数组遍历了一次。

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注