leetcode Wiggle Sort II
z
 2019-04-11 09:33:20  

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 ++;
        }
        
    }
}