LeetCode-324 Wiggle Sort II

题目描述

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

题目大意

将数组中的数字重新排序，满足nums[0] < nums[1] > nums[2] < nums[3] ...

示例

Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].

解题思路

将数组排序，依次从前到后在奇数位插入数字，从后往前在偶数位插入数字。

复杂度分析

时间复杂度：O(Nlog（N）)

空间复杂度：O(N)

代码

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