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?
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Solution 1: Use a count[32] to record counter of each bit in nums, for bit in final result, it rely on where count%3=0 or not.
public class Solution {
public int singleNumber(int[] nums) {
int[] count=new int[32];
for (int x:nums)
for (int i=0; i<32; i++)
if ((1&x>>i)==1) count[i]++;
int res=0;
for (int i=0; i<32; i++)
if (count[i]%3!=0) res|=1<<i;
return res;
}
}
没有评论:
发表评论