前言
最近感觉学习一门语言和学习算法不同，语言一定要学以致用，之前 Java 集合看过好几遍了，今天用来写ACM的时候，连HashMap怎么遍历都得现google，唉，感觉自己这学习能力低到一定程度了题目
Given an array of integers, every element appears three times except for one. Find that single one.思路
分析：给定一个数组，除了一个元素之外其它元素都出现了三次，找出这个元素（这道题的测试用例中这个元素只出现了1次）HashMap
我想大多数同学碰到这个问题都会首先考虑用HashMap，key为当前元素，value为元素出现的个数，然后遍历HashMap，找出出现次数不为3的元素即可时间复杂度为O(n),空间复杂度为O(n)
/**
* 使用HashMap解决singleNumberII问题
*
* @param A
* @return
*/
public static int singleNumberI(int[] A) {
Map
hm = new HashMap
(); int i, target = A[0]; for (i = 0; i < A.length; i++) { if (hm.containsKey(A[i])) { hm.put(A[i], hm.get(A[i]) + 1); } else { hm.put(A[i], 1); } } Iterator
> itor = hm.entrySet().iterator(); while (itor.hasNext()) { Map.Entry
entry = itor.next(); if (entry.getValue() != 3) { target = entry.getKey(); break; } } return target; }
位运算
java里int始终占4个字节，32位，我们外层循环遍历32次，然后内层循环记录0-31位每一位出现的次数，内层循环结束后将结果取余于3即为当前位的值时间复杂度O(32 * n), 空间复杂度O(1)
/**
* 利用位运算和取余实现
*
* @param A
* @return
*/
public static int singleNumberII(int[] A) {
int i, j, bit, result = 0;
for (i = 0; i < 32; i++) {
for (j = bit = 0; j < A.length; j++) {
if (((A[j] >> i) & 1) == 1) {
bit++;
}
}
bit = bit % 3;
result |= bit << i;
}
return result;
}