My O(n) time O(1) space solution


  • 3
    C
    class Solution {
    public:
        
        int singleNumber(vector<int>& nums)
        {
            typedef unsigned int uint32;
            
            uint32 single = 0;
            
            for(int nth_bit=0; nth_bit < 32; nth_bit++)
            {
                uint32 cnt = 0;
                
                for(vector<int>::size_type i = 0; i < nums.size(); i++)
                    if( (static_cast<uint32>(nums[i]) >> nth_bit) & 0x01 )
                        cnt++;
                        
                if(cnt % 3)
                    single |= (0x01 << nth_bit);
            }
            
            return static_cast<int>(single);
        }
    };

  • -1
    C

    A smart solution but not O(n).
    Note that here O(n) is an math definition which means n should be close to infinity.
    But your algo limits that n <= 2^32 * 3. The exact order of grow of your algo should be O(n*lg n) with the base of log is 2.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.