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?

解题思路：

与Single Number不同，这里不能再用异或操作来做了。可以为每个位上1的数目计数。然后将该计数%3，剩下的1肯定是单独的数字贡献的。

class Solution {
public:
    int singleNumber(vector& nums) {
        vector bitNumCount(32, 0);
        int len = nums.size();
        for(int i=0; i>1;
            }
        }
        int result = 0;
        for(int i=31; i>=0; i--){
            result = result<<1;
            if(bitNumCount[i]%3!=0){
                result += 1;
            }
        }
        return result;
    }
};

上面用了一个32位的向量。经过优化，还可以更为精简：

class Solution {
public:
    int singleNumber(vector& nums) {
        int result = 0;
        int len = nums.size();
        for(int i=0; i<32; i++){
            int count = 0;
            for(int j=0; j>i)&1;
            }
            result += (count%3)<

 
转载请注明： » [LeetCode] Single Number II

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->