C++, O(n) time, O(1) extra space. Find median.


  • 0
    X

    class Solution {
    public:
    void wiggleSort(vector<int>& nums) {
    if (nums.size() <= 1) return;

        int left = 0, right = nums.size(), target = (nums.size() + 1) / 2;
        int re;
        while (true) {
            int t = nums[left], l = left, r = right;
            while (l < r) {
                if (nums[l] <= t) l++;
                else swap(nums[l], nums[--r]);
            }
            l--;
            swap(nums[left], nums[l]);
            if (target == l - left + 1) {
                re = nums[l];
                break;
            }
            else if (target < l - left + 1) {
                right = l;
            }
            else {
                target -= l - left + 1;
                left = l + 1;
            }
        }
        
        left = 0;
        right = nums.size() - 1;
        if (right % 2 == 0) right--;
        
        for (int i = left; i < nums.size(); i += 2) {
            if (nums[i] < re) {
                nums[left] = nums[i];
                left += 2;
            }
            else if (nums[i] > re) {
                swap(nums[i], nums[right]);
                right -= 2;
                i -= 2;
            }
        }
        
        for (int i = right; i >= 0; i -= 2) {
            if (nums[i] < re) {
                nums[left] = nums[i];
    		    left += 2;
            }
            else if (nums[i] > re) {
                nums[right] = nums[i];
                right -= 2;
            }
        }
        
        for (; left < nums.size(); left += 2) nums[left] = re;
        for (; right >= 0; right -= 2) nums[right] = re;
    }
    

    };


  • 0

    You're using simple quickselect which is only O(n^2) and not O(n), no?

    Btw, your "vector& nums" causes a compile error.


Log in to reply
 

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