程序员人生 网站导航

leetcode || 137、Single Number II

栏目:框架设计时间:2015-06-01 08:47:27

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


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

最新技术推荐