/
_0324_WiggleSortII.java
74 lines (68 loc) · 2.14 KB
/
_0324_WiggleSortII.java
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package com.diguage.algorithm.leetcode;
import java.util.Arrays;
/**
* = 324. Wiggle Sort II
*
* Given an unsorted array nums, reorder it such that `nums[0] < nums[1] > nums[2] < nums[3]....`
*
* .Example 1:
* [source]
* ----
* Input: nums = [1, 5, 1, 1, 6, 4]
* Output: One possible answer is [1, 4, 1, 5, 1, 6].
* ----
*
* .Example 2:
* [source]
* ----
* 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?
*
* @author D瓜哥, https://www.diguage.com/
* @since 2020-01-26 23:29
*/
public class _0324_WiggleSortII {
/**
* Runtime: 3 ms, faster than 99.88% of Java online submissions for Wiggle Sort II.
*
* Memory Usage: 44.2 MB, less than 10.00% of Java online submissions for Wiggle Sort II.
*
* Copy from https://leetcode-cn.com/problems/wiggle-sort-ii/solution/javaxiang-xi-ti-jie-shuo-ming-by-heator/[Java详细题解说明 - 摆动排序 II - 力扣(LeetCode)]
*/
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
int length = nums.length;
int[] smaller = new int[length % 2 == 0 ? length / 2 : (length / 2 + 1)];
int[] bigger = new int[length / 2];
System.arraycopy(nums, 0, smaller, 0, smaller.length);
System.arraycopy(nums, smaller.length, bigger, 0, bigger.length);
int i = 0;
for (; i < length / 2; i++) {
int si = smaller.length - 1 - i;
nums[2 * i] = smaller[si];
int bi = length / 2 - 1 - i;
nums[2 * i + 1] = bigger[bi];
}
if (length % 2 != 0) {
nums[2 * i] = smaller[smaller.length - 1 - i];
}
}
public static void main(String[] args) {
_0324_WiggleSortII solution = new _0324_WiggleSortII();
int[] n1 = {1, 5, 1, 1, 6, 4};
solution.wiggleSort(n1);
System.out.println(Arrays.toString(n1));
int[] n2 = {1, 3, 2, 2, 3, 1};
solution.wiggleSort(n2);
System.out.println(Arrays.toString(n2));
}
}