[LeetCode] 136. Single Number

Posted on | In

Problem

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

Explanation

  1. We can use XOR to solve this problem. We know that 0 XOR 0 = 0, 1 XOR 1 = 0, 0 XOR 1 = 1 XOR 0 = 1. For example, we can initialize the res is 0000 first, loop through all the numbers, if the first number is 1010 then res XOR num = 0000 XOR 1010 = 1010. If the second number is also 1010, then res = res XOR num = 1010 XOR 1010 = 0000; If the third number is 1100, then the res = res XOR num = 0000 XOR 1100 = 1100. So we return the third number.

Solution

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