首页 > 代码库 > [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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。