leetcode-java/src/WiggleSortII324.java at master · fluency03/leetcode-java · GitHub

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
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
 *
 * Example:
 * (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
 * (2) Given nums = [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:
 * Can you do it in O(n) time and/or in-place with O(1) extra space?
 */


publicclassWiggleSortII324 {
/**
 * https://www.hrwhisper.me/leetcode-wiggle-sort-ii/
 */
publicvoidwiggleSort(int[] nums) {
Arrays.sort(nums);
int[] temp = newint[nums.length];
ints = (nums.length + 1) >> 1, t = nums.length;
for (inti = 0; i < nums.length; i++) {
temp[i] = (i & 1) == 0 ? nums[--s] : nums[--t] ;
 }

for (inti = 0; i < nums.length; i++)
nums[i] = temp[i];
 }


/**
 * https://www.hrwhisper.me/leetcode-wiggle-sort-ii/
 */
publicvoidwiggleSort2(int[] nums) {
intmedium = findMedium(nums, 0, nums.length - 1, (nums.length + 1) >> 1);
ints = 0, t = nums.length - 1 , mid_index = (nums.length + 1) >> 1;
int[] temp = newint[nums.length];
for (inti = 0; i < nums.length; i++) {
if (nums[i] < medium)
temp[s++] = nums[i];
elseif (nums[i] > medium)
temp[t--] = nums[i];
 }

while (s < mid_index) temp[s++] = medium;
while (t >= mid_index) temp[t--] = medium;

t = nums.length;
for (inti = 0; i < nums.length; i++)
nums[i] = (i & 1) == 0 ? temp[--s] : temp[--t];
 }

privateintfindMedium(int[] nums, intL, intR, intk) {
if (L >= R) returnnums[R];
inti = partition(nums, L, R);
intcnt = i - L + 1;
if (cnt == k) returnnums[i];
returncnt > k ? findMedium(nums, L, i - 1, k) : findMedium(nums, i + 1, R, k - cnt);
 }

privateintpartition(int[] nums, intL, intR) {
intval = nums[L];
inti = L, j = R + 1;
while (true) {
while (++i < R && nums[i] < val) ;
while (--j > L && nums[j] > val) ;
if (i >= j) break;
swap(nums, i, j);
 }
swap(nums, L, j);
returnj;
 }

privatevoidswap(int[] nums, inti, intj) {
inttemp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
 }


}