Share my concise solution in C++, O(n) time and O(1) memory


  • 2
    Y
    class Solution {
    public:
        vector<int> singleNumber(vector<int>& nums) {
            vector<int> result;
            if(nums.size()<2)
                return result;
            int singleTwo=nums[0];
            for(int i=1;i<nums.size();i++){
                singleTwo^=nums[i];
            }
            int first=0,second=0;
            int index=findFirstOne(singleTwo);
            for(int i=0;i<nums.size();i++){
                if((nums[i]>>index)&1){
                    first^=nums[i];
                }
                else{
                    second^=nums[i];
                }
            }
            result.push_back(first);
            result.push_back(second);
            return result;
        }
        int findFirstOne(int num){
            int index=0;
            while((num&1)==0){
                num>>=1;
                index++;
            }
            return index;
        }
    };

Log in to reply
 

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