LeetCode地址：https://leetcode.com/problems/single-number-ii/
Problem:
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?
思路
- 将数组A中每个整形的二进制 分散到一个32位数组A上求和，出现3次的在该位上的和肯定是3的倍数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public class {
public int singleNumber(int[] A) {
int ret=0,index=0;
int[] binarySum=new int[32];
if(A==null || A.length==0)
return ret;
for(int i=0;i<A.length;i++)
{
index=0;
do
{
binarySum[index++]+=A[i]%2;
A[i]/=2;
}while(A[i]!=0);
}
for(int i=0;i<binarySum.length;i++)
{
index=binarySum[i]%3;
if(Math.abs(index)>1)
{
index=(index+3)%3;
}
ret+=Math.pow(2, i)*(index);
}
return ret;
}
}
|
原文:大专栏 LeetCode-Single Number II