首页 > 代码库 > Leetcode Single Number II

Leetcode Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

对于这道题,首先想到的使用hashmap来存储数组中的数字和它出现的次数。岁日安时间为线性,但是用到了额外的空间,看人家有用位与的方法来做的,代码量也比较少,但是没有看懂。

 1 package Single.Number.II; 2  3 import java.util.HashMap; 4 import java.util.Map; 5  6 public class SingleNumberII { 7 public int singleNumber(int[] A) { 8         Map<Integer,Integer> map=new HashMap<Integer,Integer>(); 9         for(int i=0;i<A.length;i++){10             if(map.containsKey(A[i]))11             {12                 int num=map.get(A[i]);13                 num++;14                 map.remove(A[i]);15                 map.put(A[i], num);16             }else{17                 map.put(A[i], 1);18             }19         }20         int result=-1;21         for(int key:map.keySet()){22             if(map.get(key)==1)23             {24                 result=key;25                 break;26             }27         }28         return result;29     }30 }

 

Leetcode Single Number II