leetcode Wiggle Sort II

Given an unsorted array nums
, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]...
.
Example 1:
1 | Input: nums = [1, 5, 1, 1, 6, 4] |
Example 2:
1 | Input: nums = [1, 3, 2, 2, 3, 1] |
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?
- 可以对nums进行排序,之后,后半部分的肯定比前半部分的数值要打,因此,后半部分的可以放在偶数位置上面。
- 确定后半部分放在偶数位置上之后,需要确定应该正序方还是倒叙放。
- 考虑
4 5 5 6
的情况- 如果前半部分正序,后半部分倒序,结果是
4 6 5 5
- 如果前半部分正序,后半部分正序,结果是
4 5 5 6
- 如果前半部分倒序,后半部分正序,结果是
5 5 4 6
- 如果前半部分倒序,后半部分倒序,结果是
5 6 4 5
- 如果前半部分正序,后半部分倒序,结果是
- 考虑
1 | class Solution { |