Description
Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3].... You may assume the input array always has a valid answer.
Examples
Input:
nums = [1,5,1,1,6,4]Output:
[1,6,1,5,1,4]Explanation:
Satisfies nums[0] < nums[1] > nums[2] < nums[3] > nums[4] < nums[5].
Input:
nums = [1,3,2,2,3,1]Output:
[2,3,1,3,1,2]Explanation:
Valid wiggle sort arrangement.
Input:
nums = [4,5,5,6]Output:
[4,6,5,5]Explanation:
With only 4 elements, the requirement is nums[0] < nums[1] > nums[2] < nums[3]. Starting with [4,5,5,6], it is possible to arrange it as [4,6,5,5] where 4 < 6 > 5 < 5. Note that equal adjacent elements are allowed as long as the strict inequality pattern is maintained where required.
Constraints
- •
1 ≤ nums.length ≤ 5 × 10⁴ - •
0 ≤ nums[i] ≤ 5000