324 Wiggle Sort II

1. Question

Given an unsorted arraynums, reorder it such thatnums[0] < nums[1] > nums[2] < nums[3]....
Example: (1) Givennums = [1, 5, 1, 1, 6, 4], one possible answer is[1, 4, 1, 5, 1, 6]. (2) Givennums = [1, 3, 2, 2, 3, 1], one possible answer is[2, 3, 1, 3, 1, 2].
Note: You may assume all input has valid answer.
Follow Up:

2. Implementation

(1) Sort
1
class Solution {
2
public void wiggleSort(int[] nums) {
3
if (nums == null || nums.length <= 1) {
4
return;
5
}
6
7
Arrays.sort(nums);
8
int n = nums.length;
9
int[] temp = new int[n];
10
11
int low = (n + 1) / 2, high = n;
12
13
for (int i = 0; i < n; i++) {
14
temp[i] = i % 2 == 0 ? nums[--low] : nums[--high];
15
}
16
17
for (int i = 0; i < n; i++) {
18
nums[i] = temp[i];
19
}
20
}
21
}
Copied!
(2) Quick Select
1
class Solution {
2
public void wiggleSort(int[] nums) {
3
if (nums == null || nums.length <= 1) {
4
return;
5
}
6
7
int n = nums.length;
8
int median = getKthNum(nums, 0, n - 1, n/2);
9
10
int[] temp = new int[n];
11
int start = 0, end = n - 1;
12
13
for (int num : nums) {
14
if (num < median) {
15
temp[start++] = num;
16
}
17
else if (num > median) {
18
temp[end--] = num;
19
}
20
}
21
22
for (int i = start; i <= end; i++) {
23
temp[i] = median;
24
}
25
26
int low = (n + 1) / 2, high = n;
27
28
for (int i = 0; i < n; i++) {
29
nums[i] = (i % 2 == 0) ? temp[--low] : temp[--high];
30
}
31
}
32
33
public int getKthNum(int[] nums, int start, int end, int k) {
34
int pivot = partition(nums, start, end);
35
36
if (pivot < k) {
37
return getKthNum(nums, pivot + 1, end, k);
38
}
39
else if (pivot > k) {
40
return getKthNum(nums, start, pivot - 1, k);
41
}
42
else {
43
return nums[pivot];
44
}
45
}
46
47
public int partition(int[] nums, int start, int end) {
48
int mid = start + (end - start) / 2;
49
50
swap(nums, mid, end);
51
52
for (int i = start; i < end; i++) {
53
if (nums[i] < nums[end]) {
54
swap(nums, start, i);
55
++start;
56
}
57
}
58
59
swap(nums, start, end);
60
return start;
61
}
62
63
public void swap(int[] nums, int i, int j) {
64
int temp = nums[i];
65
nums[i] = nums[j];
66
nums[j] = temp;
67
}
68
}
Copied!

3. Time & Space Complexity

Sort : 时间复杂度O(nlogn), 空间复杂度O(n)
Quick Select: 时间复杂度O(n), 空间复杂度O(n)