[LeetCode OJ] Single Number之二 ——Given an array of integers, every element appears THREE times except for one. Find that single one.

浏览数：28 / 时间：2015年06月11日 

 1 class Solution {
 2 public:
 3     int singleNumber(int A[], int n) {
 4         int bits = sizeof(int)*8;
 5         int result=0;
 6         for(int i=1; i<=bits; i++)
 7         {
 8            int w=0;
 9            int t=1;
10            
11            for(int j=0; j<n; j++)
12                w += (A[j]>>(i-1))&t;
13            result+= (w%3)<<(i-1);  //若是除过一个数之外，其他数重复k次，则将此处的3改为k
14         }
15         return result;
16     }
17 };

利用二进制的位运算来解决这个问题，比如输入的数组是[2,2,3,2]

它们对应的二进制为：

0010    (2)

0010    (2)

0011    (3)

0010    (2)

————

对应位求和后：0 0 4 1

将所有的整数对应的二进制位加起来，再求除以3之后的余数，得到0011 (3)，这就是我们要找的single number。

 

对于除一个整数只出现一次，其他整数都出现k次(k=2,3,4...)，要求找到single number这种问题，也可以用上面位运算的方法来解决，只需将程序中的3改为k即可。

[LeetCode OJ] Single Number之二 ——Given an array of integers, every element appears THREE times except for one. Find that single one.,,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢