Quick Select C++ Solution


  • 9

    The idea is to split the array into three parts according to the selected pivot: left, middle and right.

    Let's say we have two indices m and n, so that all elements in [0 ... m-1] are less than the pivot, elements in [m...n] are equal to the pivot (two ends inclusive), [n+1 ... end] contains elements greater than the pivot. Then there are some facts:

    • if n - m + 1 >= 1 + nums.size()/3, nums[m] must be added to the
      results.
    • If m - 1 < 1 + nums.size()/3, we can simply abandon the left part, otherwise we have to consider it.
    • if nums.size()-n < 1+nums.size()/3, the right part can be dropped, otherwise it has to be checked.

    Ideally, we can drop about 1/3 of the array each time, so the running time is something like: 1 + 2/3 + (2/3)*(2/3) + ... = (1-(2/3)^k)/(1-2/3), O(n).

    A big advantage of this algorithm is that we can simply apply it to 1/4,1/5 ...

    class Solution {
    private:
        void split( vector<int>& nums, int left, int right, int len, vector<int>& ans ) {
            if( left >= right ) return;
            int idx = (left + right)/2, val = nums[idx], i = left+1, j=left, k=left;
            swap(nums[idx],nums[left]);
            while( i < nums.size() ) {
                if( nums[i] < val ) {
                    swap( nums[k++], nums[i]);
                    swap( nums[++j], nums[i++]);
                } else if( nums[i] == val ) {
                    swap( nums[i++], nums[++j] );
                } else i++;
            }
            if( j - k + 1 >= len ) ans.push_back(nums[k]);
            if( k - left >= len ) split(nums, left, k, len, ans );
            if( right - j >= len ) split(nums, j+1, right, len, ans );
        }
    public:
        vector<int> majorityElement(vector<int>& nums) {
            vector<int> ans;
            if( nums.empty()) return ans;
            split( nums, 0, nums.size(), 1 + nums.size()/3, ans);
            return ans;
        }
    };

  • 3
    C

    It seem that the condition of while in spilt method is wrong. it should be i < right~


  • 0

    Hi cposture,

    Thanks a lot!

    Yes, it should be i < right. It may not affect the result, but definitely slow down a little bit due to some unnecessary element check.


  • 0
    E

    This is quicksort, which does not run in linear (i.e. O(n)) time.


  • 0

    Not really. Assume you split the array into two parts, quicksort recursively checks each part till all elements are in order, and quickselect simply abandons one part. You see the difference?


  • 3
    L

    It's not a O(1) space solution, since the stack for recursive function call takes O(logn) space. Modifying the solution into a non-recursive version may solve the problem, but it still changes the input array, which cannot be thought as a O(1) space.


  • 0
    X

    The worst running time is O(n^2). The average running time is O(n), which can be calculated using Master method. The recurrence is T(n) = 2 * T(n/3) + O(n), where a = 2, b = 3, c = 1 (Case 3 in https://en.wikipedia.org/wiki/Master_theorem).


  • 1
    B

    @liangchuanzou
    Hi, liangchuanzou!
    Could you explain why is a non-recursive version still not O(1) space?


  • 0

    @liangchuanzou The average recursion depth shouldn't be O(log n) I think, because it stops early. Although I'm not sure what's the exact space complexity.


Log in to reply
 

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