A O(n) solution without XOR and extra space (with explanation)


  • 0
    Y

    I found most posts are talking about the bit operation skill.
    Here's another solution using an idea that is similar to the ones for finding median.
    We split the array in two parts by one element (left < the element < right), and if the element is not the single, then the single must be in left or right, indicated by the size being odd.
    Here is the code:

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int l = 0, r = nums.size()-1;
            int m;
            while (l < r) {
                // in order to get a more reliable O(n), one should use random
                m = (l+r) / 2;
                std::swap(nums[l], nums[m]);
                int i = l+1, j = r+1;
                // swap in order to make:
                // - left hand side < nums[l]
                // - right hand side > nums[l]
                // - nums[l+1] == nums[l]
                while (i < j) {
                    if (nums[i] == nums[l])
                        std::swap(nums[i++], nums[l+1]);
                    else if (nums[i] < nums[l]) 
                        ++i;
                    else
                        std::swap(nums[i], nums[--j]);
                }
                if (nums[l+1] != nums[l]) break;
                int lhs = i - l - 2;
                if (lhs % 2 == 1) { // the single number is in the left hand side
                    l = l+2;
                    r = i-1;
                }
                else // the single number is in the right hand side
                    l = i;
            }
            return nums[l];
        }
    };
    

Log in to reply
 

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