# 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: One possible answer is [1, 4, 1, 5, 1, 6].
Example 2:
Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].
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?
# Solution
Approach 1: Sorting.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
// time: O(nlogn); space: O(n)
// 5 4 3 2 1
// 5 4 and 3 2 1
// 3 5 2 4 1
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
std::sort(nums.begin(), nums.end(), greater<int>());
int head = 0;
int tail = n/2;
while (tail < n)
{
int tmp = nums[tail];
nums.erase(nums.begin() + tail);
nums.insert(nums.begin() + head, tmp);
head += 2;
tail++;
}
}
};
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
vector<int> sorted(nums);
std::sort(sorted.begin(), sorted.end());
int j = 0;
int k = 1;
for (int i = n - 1; i >= 0; i--) {
if (i <= (n - 1) / 2) {
nums[j] = sorted[i];
j += 2;
} else {
nums[k] = sorted[i];
k += 2;
}
}
}
};