[LeetCode] 136. Single Number

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:

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

Example 2:

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

题意是在数组里面，所有数字都成对出现，只有一个数字出现了一次。找出这个“单身”的数字。思路是用位运算的异或（XOR）。异或的特点是，当两个相同数字异或的时候结果是0；一个数字异或0，得到它本身。本题应用的是异或的第一个特性，代码如下

JavaScript实现

 1 /**
 2  * @param {number[]} nums
 3  * @return {number}
 4  */
 5 var singleNumber = function(nums) {
 6     let res = nums[0];
 7     for (let i = 1; i < nums.length; i++) {
 8         res ^= nums[i];
 9     }
10     return res;
11 };

Java实现

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