你的位置:首页 > Java教程

[Java教程][LeetCod] 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?

 

     看到这种题第一个想法就是hashset啊哈哈哈。

     根据hashset的特性,如果hashset.add()失败的话,证明这里面已经有了一个相同的值,就是说这个number不是single number了。

     所以我们判断出【不是single number】的number再将它们从hashset里面移除,那么剩下的就是我们要找的single number了。

     因为最后答案single number是在hashset中,我们并不能直接返回hashset,所以这里我们要借助iterator中的iterator().next()method。

     代码如下。~

public class Solution {  public int singleNumber(int[] nums) {    HashSet<Integer> set = new HashSet<Integer>();    for(int i=0;i<nums.length;i++){      if(!set.add(nums[i])){        set.remove(nums[i]);      }    }    return set.iterator().next();  }}