Clean average O(n) time in c++


  • 9
    W

    Although a worst case O(n) solution is available, it would make it too challenging to write during an interview. The function nth_element in C++ is readily available and is expected to have O(n) time complexity on average. Need some help, though, on how to make space complexity to be O(1).

    The algorithm is relatively straight-forward following the proof given by StefanPochmann in
    https://leetcode.com/discuss/76965/3-lines-python-with-explanation-proof

    class Solution {
    public:
        void wiggleSort(vector<int>& nums) {
            int n = nums.size();
            int mid = n/2;
            nth_element(nums.begin(), nums.begin() + mid, nums.end());
            threeWayPartition(nums, nums[mid]);
            vector<int> res(n);
            int largeStart = n-1;
            int smallStart = (n%2) ? mid : (mid-1);
            for (int i = 0; i < n; i+=2)
                res[i] = nums[smallStart--];
            for (int i = 1; i < n; i+=2)
                res[i] = nums[largeStart--];
            nums = res;
        }
        
        // this ensures all values equal to the median is in the middle
        void threeWayPartition(vector<int> &nums, int val) {
            int i = 0, j = 0;
            int n = nums.size()-1;
            while (j <= n){
                if (nums[j] < val)
                    swap(nums[i++], nums[j++]);
                else if (nums[j] > val)
                    swap(nums[j], nums[n--]);
                else
                    j++;
            }
        }
    };
    

  • 0

    "Need some help, though, on how to make space complexity to be O(1)."

    In case you mean your final part, after threeWayPartition: You can simply embed that part right into threeWayPartition like I showed here.

    In case you're worried about space complexity of nth_element... no idea :-)


  • 0

    Can you explain me why swap(nums[i++], nums[j++]) but swap(nums[j], nums[n--]) ?

    Why in the first case j++ but the second case j not change ?

    I mean why not swap(nums[j++], nums[n--]) ?

    Beside this, I want to say you should read the doc of the n-th_element() function, the result it returns has already put the smaller number on the left and the bigger number on the right.


  • 0
    W

    You can see j as the the start index of the value in the middle that has not been processed, i is the start index of value that is processed and equals to val or not processed (this case equals to j). n is one before the star index of processed value that is > val. Hope this helps and you can also take a look at the wiki page https://en.wikipedia.org/wiki/Dutch_national_flag_problem


  • 0

    @RainbowGay

    you should read the doc of the n-th_element() function, the result it returns has already put the smaller number on the left and the bigger number on the right.

    What's your point? The way nth_element does it isn't enough.


  • 0
    2

    @StefanPochmann

    What I mean is that nth_element put all the smaller number before and bigger after the pos. But the order of both size is messy ! So the key is that in the bigger side of the returned result. There maybe the equal one, the API won't put the equal one on the small position.

    like this:

    Input : 6 5 4 5 5

    After the nth_element() n=5 mid=2
    The returned result might be like this:

      4  5 [5]  6  5
    

    So you know we want is like

    4 5 5 5 6

    So, your threeParition() is redundant in some sense, You only need to resort the equal one before bigger one on the larger side.


  • 0
    2

    @StefanPochmann

    You can refer the official doc

    " The other elements are left without any specific order, except that none of the elements preceding nth are greater than it, and none of the elements following it are less. "

    link : http://www.cplusplus.com/reference/algorithm/nth_element/


  • 0
    I

    WOuld they really expect us to come up with this in an interview? It seems somewhat complicated :O


  • 0

    @RainbowSomething I know what nth_element does, but I didn't realize the lower and upper half could then be treated independently here. I'm not convinced it's better, though, as you still need to process both halves, i.e., the whole array. Are two two-way partitions really better than one three-way partition? Anyway, while thinking about that, I realized an improvement for another solution. Thanks :-)


  • 0

    I have noticed that two-way partitions usually run faster than three-way (probably because of less comparisons), so it may be reasonable. Especially in this case, where we only need to move equal elements towards the center.


  • 0

    @stachenov You get my points


  • 0
    A

    I tried to not use a new vector, and tested for a while, which don't give the right answer. I don't know why. Is it because the "gap" is wrong?

    int gap = (n-1)/2;
            for (int i = 1; i+gap < n; i += 2) {
                swap(nums[i], nums[i+gap]);
                cout << "swap " << i << " -- " << i+gap << endl; 
            }

Log in to reply
 

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