324

O(nlogn) time, O(1) space

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> sorted(nums);
        sort(sorted.rbegin(), sorted.rend());
        int n = nums.size(), m = n | 1;
        for(int i=0; i<n; i++)
            nums[(1+2*i)%m] = sorted[i];
    }
};

---------------
O(n) time, O(1) space

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

        // Step 1: Find the median
        vector<int>::iterator nth = next(nums.begin(), n / 2);
        nth_element(nums.begin(), nth, nums.end());
        int median = *nth;

        // Step 2: Tripartie partition within O(n)-time & O(1)-space.
        auto m = [n](int idx) { return (2 * idx + 1) % (n | 1); };
        int first = 0, mid = 0, last = n - 1;
        while (mid <= last) {
            if (nums[m(mid)] > median) {
                swap(nums[m(first)], nums[m(mid)]);
                ++first;
                ++mid;
            }
            else if (nums[m(mid)] < median) {
                swap(nums[m(mid)], nums[m(last)]);
                --last;
            }
            else {
                ++mid;
            }
        }
    }
};