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?
Problem Analysis:
Suppose the array is sorted, with index from 0 to n-1, we can partition it with 2 part, pre part is [0, middle), another is [middle, n). Then the array with index 0, middle, 1, middle + 1, … is an answer.
Sort array is O(nlgn) time complexity. So we can simply partition the array into 2 parts without sorting, it is O(n) time complexity. Then we reindex the array by fetching item from the two parts alternately.
Solution:
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
auto mid_it = nums.begin() + n / 2;
nth_element(nums.begin(), mid_it, nums.end());
int middle = *mid_it;
#define A(i) nums[(1 + (i) * 2) % (n | 1)]
int i = 0, j = 0, k = n - 1;
while (j <= k) {
if (A(j) > middle) swap(A(i++), A(j++));
else if (A(j) < middle) swap(A(j), A(k--));
else ++j;
}
}
};Note that the macro A(i), A(0), A(1), …, A(n-1) means nums[1], nums[3], nums[5], nums[7], …, nums[0], nums[2], nums[4], nums[6], …
Time Complexity: O(nlgn)
Space Complexity: O(1)