A general way to solve this kind of problem using 3-way partition (without bit operations) in C++


  • 0
    Y

    To avoid bit operations, one can use 3-way partition as a solution. (with O(n) in average)
    Constant space. The algorithm will modify the array in place.
    The idea is to split the array in three part using a pivot (<pivot, =pivot, >pivot), and the single must be in one of the three parts, indicated by the remainder by 3 (or 4,5,6, etc.) being 1 while the other two parts have remainders by 3 being 0.

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int l = 0, r = nums.size()-1;
            while (l < r) {
                // in order to get a more reliable O(n)
                // one should choose a random position
                int pivot = nums[(l+r)/2];
                int lower = l, middle = l, upper = r;
                // swap in order to make:
                // - lhs: nums[l..lower-1] < pivot
                // - mid: nums[lower..middle-1] == pivot
                // - rhs: nums[middle..r] > pivot
                while (middle <= upper) {
                    if (nums[middle] < pivot)
                        std::swap(nums[lower++], nums[middle++]);
                    else if (nums[middle] > pivot)
                        std::swap(nums[middle], nums[upper--]);
                    else
                        ++middle;
                }
                int lhs = lower - l;
                // int mid = middle - lower;
                int rhs = r - middle + 1;
                if (lhs % 3 == 1) // if single is in lhs
                    r = lower-1;
                else if (rhs % 3 == 1) // if single is in rhs
                    l = middle;
                else { // else, it's in mid
                    l = lower;
                    r = middle - 1;
                }
            }
            return nums[l];
        }
    };```

Log in to reply
 

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