国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php框架 > 框架设计 > leetcode || 137、Single Number II

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; } };


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生