September 19, 2016 算法/Algorithms No comments

Question: Given an array of integers, every element appears

twiceexcept for one. Find that single one.

For this question, there should be several fairly simple naive approaches.

For example, for every element in the list, we compare it with all other elements in the list. If there is an element which does not have a “sibling”, then this element is the one which we should return.

However, the approach above is **NOT** efficient, it has a time complexity of **O(n^2)** since every element needs to compare to the whole array. When the array is large enough…… SLOW!

Now, the question is, how should we make it** FASTER**, is it possible to make it run in **O(n)**?

Let’s think about it. Two is always an interesting number. In order to make the algorithm finish in **O(n)** time. We probably need to find a way to make those two values **“cancel out”**.

Cancelling out two same values… Um… O(n)… OH!!!! What about **BIT OPERATION**!

**0000 xor 1111 = 1111**

**1111 xor 1111 = 0000**

That’s definitely what we want!

**So, we define a variable “result”, then we just xor the first number with 0 and store it to “result” and xor every number after that with the previous “result” and store it back to “result”. After one traversal, guess what we get? We get that little poor lonely ****value!**

Java: public class Solution { public int singleNumber(int[] nums) { int result = 0; for(int i = 0; i < nums.length; i++){ result ^= nums[i]; } return result; } }

**That’s it!**