题目
给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。
样例
给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4
挑战
一次遍历，常数级的额外空间复杂度
解题
可以利用HashMap直接解决，时间复杂度和空间复杂度都是O(N)
1.map中存在该元素则：map.put(num,map.get(num) + 1)
2.map中不存在该元素则：map.put(num , 1)
3.map中这个元素出现次数等于三次，则删除该元素
空间复杂度最坏的情况是O(N*2/3)
public class Solution {
/**
* @param A : An integer array
* @return : An integer
*/
public int singleNumberII(int[] A) {
// write your code here
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
int single = 0 ;
for(int i=0;i<A.length;i++){
if(map.containsKey(A[i])){
map.put(A[i],map.get(A[i]) + 1);
}else{
map.put(A[i],1);
}
if(map.get(A[i]) == 3){
map.remove(A[i]);
}
}
Set<Integer> keySet = map.keySet();
for( Integer num:keySet){
single = num;
}
return single;
}
}
Java Code
总耗时: 2647 ms
这个方法不是很好，空间复杂度不是O(1)
上面Hashmap在put的适合都要根据key计算hashcode，再计算位置，再根据所在链表顺序更新，效率不高
在*上，value用数组定义，或者自己定义一个引用类型变量，但是上面说的数组效率最高
import java.util.*;
public class Solution {
/**
* @param A : An integer array
* @return : An integer
*/
public int singleNumberII(int[] A) {
// write your code here
HashMap<Integer,int[]> map = new HashMap<Integer,int[]>(); // 数组存储效率高
for(int i=0;i<A.length;i++){
int[] value = map.get(A[i]);
if(value==null){
map.put(A[i],new int[]{1});
}else{
value[0]++; // 直接+1
}
}
for(Map.Entry<Integer,int[]> entry:map.entrySet()){
int[] value = entry.getValue();
if(value[0]==1){
return entry.getKey();
}
}
return -1;
}
}
当a出现一次的时候，ones能保存a。当a出现两次的时候，twos能保存a。
当a出现三次的时候，ones和twos都清零。
所以，如果一个数值中所有的数都通过这个循环的话，出现三次的数都清零了，
有一个数如果出现一次，它保存在ones中；如果出现两次的话保存在twos中。
public class Solution {
/**
* @param A : An integer array
* @return : An integer
*/
public int singleNumberII(int[] A) {
// write your code here
int ones = 0;
int twos = 0;
for(int i=0;i< A.length ;i++){
ones = (ones^A[i]) & (~ twos);
twos = (twos^A[i]) & (~ ones);
}
return ones;
}
}
Java Code
总耗时: 246 ms
class Solution:
"""
@param A : An integer array
@return : An integer
"""
def singleNumberII(self, A):
# write your code here
ones = 0
twos = 0
for num in A:
ones = (ones ^ num) & (~twos)
twos = (twos ^ num) & (~ones)
return ones
Python Code
总耗时: 258 ms
表示不理解。。。