Single Number, Leetcode 解题笔记

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?

第一反应就应该是bit操作。当然也可以用hashmap,但是会用额外空间。

复习一下XOR的性质:A XOR A = 0; A XOR B XOR A = B

public class Solution {
    public int singleNumber(int[] A) {
        int sum = 0;
        for(int i = 0; i < A.length; i++){
            sum = sum ^ A[i];
        }
        return sum;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s