O(n) time and cheating O(1) space solution, will there be a real O(1) solution?


  • 4
    A
    class Solution {
    public:
        void wiggleSort(vector<int>& nums) {
            // Only four Line
            if (2>(n = nums.size())) return;
            r_start = n/2;
            dfs(nums, find_medin(nums));
            re_order(nums);
        }
    private:
        int n;
        int r_start;
            int pivot(vector<int> &nums, int i, int j) {
            assert(i<j);
            swap(nums[i],nums[(i+j)/2]);
            int idx = i++;
            int val = nums[idx];
            while (i<j) {
                if (nums[i]<=val) i++;
                else if (nums[j]>=val) j--;
                else swap(nums[i],nums[j]);
            }
            if (nums[i]>val) i--;
            if (nums[i] != nums[idx]) swap(nums[i], nums[idx]);
            return i;
        }
        
        double find_kth(vector<int> &nums, int k) {
            int i = 0, j = n-1;
            while (i<j) {
                int m = pivot(nums,i,j);
                int len = m-i+1;
                if (k<len) {
                    j = m-1;
                } else if (k>len) {
                    k-=len;
                    i = m+1;
                } else {
                    return nums[m];
                }
            }
            return nums[i];
        }
        
        double find_medin(vector<int> &nums) {
            if (n&1) {
                return find_kth(nums, 1+(n>>1));
            } else {
                return (find_kth(nums,n>>1) + find_kth(nums, 1+(n>>1)))/2;
            }
        }
        
        //Dutch Flag Srot (reversed order)
        void dfs(vector<int> &nums, double target) {
            int i = 0, j = n-1, k = 0;
            while (k<=j) {
                if (nums[k]>target) {
                    swap(nums[i++], nums[k++]);
                } else if (nums[k] < target) {
                    swap(nums[j--], nums[k]);
                } else {
                    k++;
                }
            }
        }
    
        int get_next(int i) {
            if (i>=r_start) return (i-r_start)<<1;
            else return 1+(i<<1);
        }
        // giving up to think a legitimate O(1) space solution.
        // cheat by using a mask to show whether it has 
        // been visited or not. This sub-problem is much harder compare
        // to array rotation, I cannot use a count and increase
        // the start by one whenever count < limit.
        void re_order(vector<int> & nums) {
            for (int mask = 1<<30, i, temp, start=0; start<n; ++start) {
                if (!(nums[start] & mask)) {
                    temp = nums[i = start];
                    do {swap(temp|=mask, nums[i=get_next(i)]);} while (i!=start);
                }
                nums[start] ^= mask;
            }
        }
    };

  • 5

    That final reordering in O(1) space is easy. Just embed it into your dfs by treating i, j and k as virtual indexes and rewiring them to the appropriate real indexes:

    //Dutch Flag Srot (reversed order)
    void dfs(vector<int> &nums, double target) {
        int i = 0, j = n-1, k = 0, N = n|1;
        #define Nums(i) nums[(1+2*(i)) % N]
        while (k<=j) {
            if (Nums(k) > target) {
                swap(Nums(i++), Nums(k++));
            } else if (Nums(k) < target) {
                swap(Nums(j--), Nums(k));
            } else {
                k++;
            }
        }
    }
    

    To be clear: This replaces your re_order and get_next, which you then must not use anymore.

    My question is "will there be a real O(n) time solution?". Because yours, like the others that claim this, is only O(n^2), not O(n).


  • 0

    real O(n) can be achieved if we use "median of medians"wiki, to find the median.
    It has worst case O(n) time performance with O(1) space


  • 0

    Yes, I know. I'm just wondering whether anybody will bother to actually do that :-)
    Using simple quickselect and falsely claiming O(n) seems much more popular :-(


  • 0

    That is true.


  • 0
    A

    Thanks for you answer. First thing learned in 2016! Happy new year!
    BTW: this solution is average O(n) time.


  • -1
    E

    if you get [2,2,2,2,1,1,1],after the three way partition, will you get [2,2,1,2,1,2,1]


  • 0

    @Enzhou Well, please show us a valid answer to your input [2,2,2,2,1,1,1].


  • 0
    This post is deleted!

  • 0
    B

    @dietpepsi But even median of medians has a O(lgn) recursion depth which consumes program stack space.


Log in to reply
 

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