Link to original question

Given an unsorted array nums, reorder it such that nums[0] < nums[1] &> nums[2] < nums[3]…. Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

The most intuitive way to solve this problem is to arrange the array in order first, and then do the exchange. I didn’t study the specific exchange method, but in theory, it must be arranged in O (n) time and O (1) space. However, the bottleneck is that the fastest sorting method can’t do o (n), so this method doesn’t work. So I relaxed the restrictions. Even if I didn’t sort the array, if I could try to divide the values of the array into two groups, and any value in one group was not less than any value in the other group, I would put the larger group in odd digits and the smaller group in even digits, which would also meet the requirements of the topic. Obviously, the cut-off value of the two groups can use the median (not the average), so the bottleneck is the complexity of finding the median. It happens that C + + provides nth_ The element method can find the nth largest value in the array , which has o (n) time complexity and O (1) space complexity.

After finding the median, the array is divided into three categories: greater than median (L), less than median (s), and equal to median (m). Obviously, when traversing an array, s should be placed in even digits, l in odd digits, and m in the rest. If the even and odd digits are filled in the order from front to back, then for the array composed of two s, two L and two m, SLMM arrangement may be formed, that is, the median is stacked at the end. Therefore, even and odd bits should be filled in the opposite order. For example, my method is that odd bits are filled from front to back, and even bits are filled from back to front, so that they can be arranged into smslml.

class Solution {
public:
    void wiggleSort(vector<int&>& nums) {
        int n = nums.size();
        if(n<2) return;
        // Find a median
        auto midptr = nums.begin() + n/2;
        nth_element(nums.begin(), midptr, nums.end());// O(n) time, O(1) space
        int mid = *midptr;
        
        int j=1;// first odd
        int k=(n%2==0)?n-2:n-1;// last even
        int i=1;// start from first odd
        for(int count=0; count<n; count++) {
            if(nums[i]<mid) {
                swap(nums[i], nums[k]);
                k=k-2;
            }
            else if(nums[i]&>mid) {
                swap(nums[i], nums[j]);
                j=j+2;
                i=i+2;
                if(i&>n-1) i=0;// back to first even;
            }
            else {
                i=i+2;
                if(i&>n-1) i=0;
            }
        }
    }
};

The exchange value method of O (1): starting from the first odd digit (marked with I), the goal is to change all odd digits into values not less than the median. mark the location where the first s should be stored with K, and mark the location where the first l should be stored with J .

1. If the value of the current odd digit is less than the median, it is swapped to K. As mentioned above, K is moved from the last even bit to the front, so K-2 after swapping. Because I don’t know what the value is, I don’t need to move.

2. If the value of the current odd digit is equal to the median, do not move it, I move backward.

3. If the value of the current odd digit is larger than the median, it is swapped to J. Because I &> = J, the value I accessed by J must also be accessed. According to the operation of 1 and 2, the value accessed by I must not be smaller than the median value, so the value returned by the current bit exchange must not be smaller than the median value. After the exchange, I and j move backward. In fact, the purpose of this operation is to move the median to the last odd digit.

Finally, llllsmsm may appear after traversing odd digits, so even digits need to be traversed once. Note that even bits should be traversed from front to back, opposite to the change direction of K. This is to avoid revisiting the position visited by K (which will cause the correct value to be removed).