« Back
in Hash Table Bit Manipulation read.

Leetcode 136 Single Number.

Problem 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?

First time when I saw this problem, I felt confusing, and the first way to deal with it is using tradition way to separate the number into digits. But that would fail, because of the run time will exceed the limit.

I have to find the answer from the google.

Obviously, it is not so hard if you have deal with this kind of problem before.

If use the ^, then the problem would be very easy to be done.

if one digit appear twice, then the ^ will make the result be 0. But if it only appear once, then the result would be the number.

But there are some problems here. Cause the number we are not sure how many times it appears, when it appear 3 times, it would still in the result. Won't affect the result for this problem.

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

comments powered by Disqus