Question

Formatted question description: https://leetcode.ca/all/136.html

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?

Algorithm

Set

The direct idea is to use HashSet to use its constant search speed. Traverse each number in the array, if the current number is already in the HashSet, remove the number in the HashSet, otherwise add it to the HashSet.

This is equivalent to offsetting two by two. In the end, all the numbers that appear twice are removed from the HashSet, and the only one left is a single number.

Bit

Since numbers are stored in binary in the computer, each bit is 0 or 1. If we XOR two identical numbers, the exclusive OR of 0 and 0 is 0, and the exclusive OR of 1 and 1 is also 0.

Then if we XOR all the numbers in the array, and each pair of the same number will get 0, and then the last remaining number is the number that has only one time.

  1. num^num = 0
  2. careful about the initiation of sum, it should be 0
    • just use a simple test case to find it out

Code

Java

  • 
public class Single_Number {

    public class Solution {
        public int singleNumber(int[] nums) {

            if (nums == null || nums.length == 0) {
                return -1;
            }

            int a = nums[0];
            for (int i = 1; i < nums.length; i++) {
                a ^= nums[i];
            }

            return a;
        }
    }
}

  • // OJ: https://leetcode.com/problems/single-number/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int n : nums) ans ^= n;
        return ans;
    }
};

  • class Solution(object):
  def singleNumber(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    for i in range(1, len(nums)):
      nums[0] ^= nums[i]
    return nums[0]

All Problems

All Solutions