LeetCode 324. Wiggle Sort II

Given an unsorted array nums , reorder it such that nums[0] < nums[1] > nums[2] < nums[3] … .

Example 1:

Input: nums = [1,5,1,1,6,4]
Output: nums = [1, 4, 1, 5, 1, 6] 

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1]
Output: [2 ,3, 1, 3].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

解析：数组摆动排序，最开始的思路是先将数组排序，然后从中间位置开始依次取前一个数和后一个数，后来发现对于存在多个相同的数值，这种不满足要求。正确的解法是先对数组排序，然后将数组分为两部分，分别取前半段的最后一个后半段的最后一个，依次处理。代码如下：

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> result = nums;
        sort(result.begin(), result.end());
        int size = nums.size();
        int j = size, k = (size+1)/2;
        for(int i=0; i < size; i++)
        {
            int num = i % 2 ==0? result[--k]:result[--j];
            nums[i] = num;
        }
    }
};