首页 > 代码库 > [leetcode]Single Number II

[leetcode]Single Number II

2024-07-16 08:57:04   220人阅读

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

 


联系
我们