Single Number II
今天是一道有关数学和位运算的题目，来自LeetCode#137，难度为Medium，Acceptance为35.7%。该题是Single Number（回复008查看）的进阶。
题目如下
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?
解题思路及代码见阅读原文
回复0000查看更多题目
解题思路
首先，在Single Number一题中，直接利用位运算中的异或运算就可以得到最后的结果，那么，在该题中能否也这样做呢，显然是不能的，那么这里应该怎么做呢？
其实这题的解题思路很多：
思路一，可以先排序，然后计算相邻的数是不是出现三次就可以，那么这种方法的时间复杂度就是排序算法的时间复杂度O(logn)。
思路二，首先开辟这样一个数组mark[32]表示一个整数的32个二进制位（因为这里是int类型，32位已经够用）；然后遍历数组中的每一个数字，将其每一等于1的二进制位加到相应的mark数组中；这样若mark中任意一个元素对3取余不为0，则该位必在Single Number中也不为0，即为1；最后，将各个二进制位拼接起来就可以得到最后的结果。这样的时间复杂度为O(n)。其实还有更为简洁的解法，但这种方法更为通用。
下面我们给出思路二的代码
代码如下
java版
public class Solution {
/**
* @param A : An integer array
* @return : An integer
*/
public int singleNumberII(int[] A) {
// write your code here
int[] mark = new int[32];
for(int i = 0; i < A.length; i++) {
for(int j = 0; j < 32; j++) {
mark[j] += (A[i] & (1 << j)) == 0 ? 0 : 1;
}
}
int ans = 0;
for(int i = 0; i < 32; i++) {
if(mark[i] % 3 != 0) {
ans += (1 << i);
}
}
return ans;
}
}
关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助
image
