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?

思路: 非space0(n)解法,用hashTable。 注意Java的hashMap的遍历API。
Space 0(n)的解法, 数字成对出现找落单,用XOR的性质, 0^X=X;X^X=0;初始result=0,去挨个XOR数组里面的数,最后就是单个数的结果。

public class Solution {
    public int singleNumber(int[] nums) {
        int result = nums[0];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                int count = map.get(nums[i]);
                map.put(nums[i], count + 1);
            }
        }

        Set set = map.entrySet();
        Iterator iter = set.iterator();
        while(iter.hasNext()) {
            Map.Entry me = (Map.Entry) iter.next();
            if ((int)me.getValue() == 1) {
                result =(int) me.getKey();
            }
        }
        return result;
    }
}

space: o(1)

public class Solution {
    public int singleNumber(int[] nums) {
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            result = result ^ nums[i];
        }
        return result;
    }
}
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