Single Number

Tags: Hash Table, Bit Manipulation, Easy

Question

Problem Statement

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?

题解

「找单数」系列题，技巧性较强，需要灵活运用位运算的特性。根据题意，共有2*n + 1个数，且有且仅有一个数落单，要找出相应的「单数」。鉴于有空间复杂度的要求，不可能使用另外一个数组来保存每个数出现的次数，考虑到异或运算的特性，根据x ^ x = 0和x ^ 0 = x可将给定数组的所有数依次异或，最后保留的即为结果。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: Array of integers.
  5.      * return: The single number.
  6.      */
  7.     int singleNumber(vector<int> &A) {
  8.         if (A.empty()) {
  9.             return -1;
  10.         }
  11.         int result = 0;
  13.         for (vector<int>::iterator iter = A.begin(); iter != A.end(); ++iter) {
  14.             result = result ^ *iter;
  15.         }
  17.         return result;
  18.     }
  19. };

Java

  1. public class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         if (nums == null || nums.length == 0) return -1;
  5.         int result = 0;
  6.         for (int num : nums) {
  7.             result ^= num;
  8.         }
  10.         return result;
  11.     }
  12. }

源码分析

  1. 异常处理(OJ上对于空vector的期望结果为0，但个人认为-1更为合理)
  2. 初始化返回结果result为0，因为x ^ 0 = x