leetcode || 137、Single Number II
来源:程序员人生 发布时间:2015-06-01 08:47:27 阅读次数:3793次
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?
Hide Tags
Bit Manipulation
题意:1个数组中,只有1个元素出现1次,其他元素出现K次,(k为奇数3)
thinking:
(1)这道题适用于出现奇次的情形,解法是:对数组所有数的每位出现1的次数进行统计,对K取余后,就为待求数在该位的位数(0或1),
再将2进制转换为10进制便可
(2)这道题我假定int为32位,有些机器不是32位。
code:
class Solution {
public:
int singleNumber(vector<int>& nums) {
string s;
int a=0x0001;
int count=0;
for(int i=0;i<32;i++)
{
for(int j=0;j<nums.size();j++)
{
if((nums[j]&a)!=0)
count++;
}
s.push_back('0'+count%3);
a=a<<1;
count=0;
}
return reverse_string_to_int(s);
}
protected:
int reverse_string_to_int(string s)
{
int a=1;
int ret=0;
for(int i=0;i<s.size();i++)
{
ret+=(s.at(i)-'0')*a;
a*=2;
}
return ret;
}
};
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠