您当前位置：首页 > php框架 > 框架设计 > leetcode || 137、Single Number II

leetcode || 137、Single Number II

来源：程序员人生发布时间：2015-06-01 08:47:27 阅读次数：3714次

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

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

------分隔线----------------------------

上一篇 6 UVA 10252 Common Permutation

下一篇 第八周（字符串类）

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点