[LeetCode] 324. 摆动排序 II

[Animenzzzz]

题目描述：

给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

示例 1:

输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]

示例 2:

输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]

说明:
你可以假设所有输入都会得到有效的结果。

进阶:
你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

解题思路：首先给数组排序，然后将数组分成两半，使用k,j两个索引代表分别前半段和后半段的末尾。然后开始重新赋值，当遇到nums的下标为偶数时，重前半段的末尾取值，为奇数时，从后半段的末尾取

C++解题：

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