O(n) time achieved but don't know how to get O(1) space (except virtual indexing)


  • 0
    Q

    I can make the nums array to be equivalent to sorted (by pulling the median values at the center in O(n) time), but looks like it is impossible to rearrange nums without using any buffer. Too complicated. Does anyone know? Thanks.

    class Solution {
    public:
    void wiggleSort(vector<int>& nums) {
    int n = nums.size();
    if(n <= 1) return;
    if(n == 2) {
    if(nums[0]> nums[1]) swap( nums[0], nums[1]);
    return;
    }

        //nth_element(nums, (n+1)/2, 0, n-1);
        std::nth_element(nums.begin(), nums.begin()+ n/2, nums.end());
        // 1, 1 , 1, 4,5, 6
        int mid = n/2;
        int midval = nums[mid];
        int i,j;
        for(i =mid -1, j = mid-1; i >= 0 && j >=0; --i) {  //pull mid to the end of first half. both i, j start from back!!!
            if(nums[i] == midval) {
                if( i!=j) swap(nums[i], nums[j]);
                j--;
            }
        }
        for(i = mid, j = mid; i <n; ++i)   //pull mid to the begin of first half
        {
            if(nums[i] == midval)
            {
                if(i!= j)  swap(nums[i], nums[j]);
                ++j;
            }
        }
        
        // for(int i = 0, j = (n+1)/2; j < n; i++, j++) {
        //   swap(  nums[j], nums[i*2+1]);
    
        // }
        
        vector<int> res(n);
        int endOfHalf = ((n%2)==0) ? mid-1 : mid;
        for(i = endOfHalf ; i >= 0; i--) {
            res[(endOfHalf - i)*2] = nums[i];
        }
        for(i = n-1; i> endOfHalf; --i) {
            
            res[(n-1- i)*2+1] = nums[i];
        }
        
        nums = res;
      return;
    

    }

        return;    
    }};

  • 0
    Q

    @quesder
    this comment is wrong. //pull mid to the begin of first half
    should be //pull mid to the beginning of second half.


  • 0

Log in to reply
 

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