共计 710 个字符，预计需要花费 2 分钟才能阅读完成。
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2]Output: 3Example 2:
Input: [0,1,0,1,0,1,99]Output: 99
难度: medium
题目：给定一个非空整数数组，其中一个元素出现一次，其它元素出现三次。找出有且仅出现一次的那个元素。注意：你的算法时间复杂度为 O(n)。能否实现它不使用额外的内存？
思路：按位统计各个元素中位出现的次数，因为除 1 次出现的元素之外，其它元素都出现 3 次，因此按位统计位 1 和位 0 的个数应为 3 的倍数。最后只出现 1 次的那个元素的所有位都会剩下来。
Runtime: 3 ms, faster than 60.00% of Java online submissions for Single Number II.
class Solution {
public int singleNumber(int[] nums) {
int result = 0, bit = 0;
for (int i = 0; i < 32; i++, bit = 0) {
for (int j = 0; j < nums.length; j++) {
bit += (nums[j] >> i) & 1;
bit %= 3;
}
result |= (bit << i);
}
return result;
}
}
