Single Number leetcode java

问题描述：

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不同时，返回1。如果两个数是相同的，异或运算将会返回0。

nums中只含有一个single number，因此，采用异或运算，最后得到的就是所求的single number。

public int singleNumber(int[] nums){

      int single = 0; 

      for(int i = 0; i < nums.length; i ++)

           single = single ^ nums[i];

      return single;

}

二、hashset

相比于hashtable，hashmap存储的是key-value键值对，hashset直接操作对象，且不允许存储重复元素。

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]); //删除重复元素

      Iterator<Integer> iterator = set.iterator(); //迭代器，遍历set

      return iterator.next();

}

巴特西

Single Number leetcode java

最新文章

热门文章