首页 > 代码库 > [LeetCode] 136.Single Number Java

[LeetCode] 136.Single Number Java

题目:Given an array of integers, every element appears twice except for one. Find that single one.

题意及分析:一个数组中,有一个数只出现了一次,其他的出现了两次。要求给出只出现一次的数。这道题,最简单的方法是用一个hashtable来储存,然后得出结果,但是效率比较低。也可以用位运算求解。直接使用异或运算,因为对于异或运算有:n^0=n,n^n=0,所以相同的数异或为0,最后得出的结果就为出现一次的数。

位运算常用技巧:
(1)n & (n-1)能够消灭n中最右侧的一个1。
(2) 右移:除以2, 左移:乘以2。
(3)异或性质:交换律,0^a=a, a^a=0;
使用hashtable,主要是看hashtable怎么遍历:
import java.util.Enumeration;
import java.util.Hashtable;
public class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length==0) return 0;
        Hashtable<Integer,Integer> res = new Hashtable<>();
        for(int i=0;i<nums.length;i++){
            if(!res.containsKey(nums[i])){
                res.put(nums[i],1);
            } else{
                res.remove(nums[i]);
                res.put(nums[i],2);
            }
        }

        Enumeration e = res.keys();
        while( e.hasMoreElements() ){
            Object x =e.nextElement();
            if(res.get(x)==1){
                return (int)x;
            }
        }
        return 0;
    }
}

 使用位运算:

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

 

  

 

[LeetCode] 136.Single Number Java