leetcode Wiggle Sort II
z

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

Example 1:

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

Example 2:

1
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?


  • 可以对nums进行排序,之后,后半部分的肯定比前半部分的数值要打,因此,后半部分的可以放在偶数位置上面。
  • 确定后半部分放在偶数位置上之后,需要确定应该正序方还是倒叙放。
    • 考虑4 5 5 6的情况
      • 如果前半部分正序,后半部分倒序,结果是4 6 5 5
      • 如果前半部分正序,后半部分正序,结果是4 5 5 6
      • 如果前半部分倒序,后半部分正序,结果是5 5 4 6
      • 如果前半部分倒序,后半部分倒序,结果是5 6 4 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public void wiggleSort(int[] nums) {
int [] copy = new int[nums.length];
for (int i=0; i<nums.length; i++) {
copy[i] = nums[i];
}

Arrays.sort(copy);
int i = (nums.length-1)/2;
int j = nums.length-1;
int idx = 0;
while (idx < nums.length) {
if (idx % 2 == 0) {
nums[idx] = copy[i];
i-=1;
}
else {
nums[idx] = copy[j];
j-=1;
}
idx ++;
}

}
}