LeetCode136 Single Number

• Given an array of integers, every element appears twice except for one. Find that single one.
  • Notice:Your algorithm should have a linear runtime complexity. Implement it without using extra memory.
• Analysis:
  • The problem itself is not hard. However, the additional time and spcace overhead limitation is a bit annoying. I have no clue at the first sight of this probelm,either. I finally solve it by referring to others‘ solutions, which reminds me that xor operation is the key to the problem.
  • We all know A^A equals to zero, then we can xor all the numbers and the final answer will be the number appeaing just once.
• Code:

•  1 class Solution {
   2 public:
   3     int singleNumber(int A[], int n) {
   4         int ans = 0;
   5         for (int i = 0; i < n; i++){
   6             ans ^= A[i];             //xor
   7         }
   8         return ans;
   9     }
  10 };

   

• Actually, the code works well not only for appearing twice, but also appearing even times.
• In next bolg, I will share you will a more general way to handle this kind of question.

LeetCode136 Single Number

原文：http://www.cnblogs.com/easy-busy/p/4415204.html