首页 > 代码库 > [leetcode]Single Number II
[leetcode]Single Number II
Single Number II
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?
算法思路:
思路1:用一个数组来模拟CPU位数,记录int类型的32位中每一位出现的次数,容易理解,可惜的是没有达到题中要求的O(1)空间。
1 public class Solution { 2 public int singleNumber(int[] a) { 3 int[] binary = new int[32]; 4 for(int tem : a){ 5 int bin = 1; 6 for(int i = 0; i < 32; i++){ 7 if((tem & bin) == bin) 8 binary[i]++; 9 bin = bin << 1;10 }11 }12 int res = 0;13 for(int i = 0; i < 32; i++){14 res |= (binary[i] % 3) << i;15 }16 return res;17 }18 }
思路2:对思路1的优化,对每一位进行数组的遍历,求出该位出现的次数,然后%3取模,对结果的该位进行赋值。
1 public class Solution { 2 public int singleNumber(int[] a) { 3 int res = 0; 4 for(int i = 0; i < 32; i++){ 5 int binary = 1 << i; 6 int count = 0; 7 for(int tem: a){ 8 if((tem & binary) != 0){ 9 count++;10 } 11 }12 res |= (count % 3) << i;13 }14 return res;15 }16 }
参考资料:http://www.cnblogs.com/jdflyfly/p/3828929.html
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。