Leetcode(136) Single Number

发表于 | 分类于

Description

Given a non-empty 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?

Example 1:

1
2
Input: [2,2,1]
Output: 1

Example 2:

1
2
Input: [4,1,2,1,2]
Output: 4

解法

这个题的思路太巧妙了。利用异或这个运算有三个很重要的特性：

  • 两个相同的数异或后为0；
  • 0和一个数异或后为那个数；
  • 异或运算满足交换律。

所以利用0与各位置上的数进行异或运算即可得到最终的只出现过一次的结果

具体代码如下：

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0;i<nums.length;i++){
            res ^= nums[i];
        }
        return res;
    }
}