Description#
Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
You may assume the input array always has a valid answer.
Example 1:
Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.
Example 2:
Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]
Constraints:
1 <= nums.length <= 5 * 1040 <= nums[i] <= 5000- It is guaranteed that there will be an answer for the given input
nums.
Follow Up: Can you do it in
O(n) time and/or
in-place with
O(1) extra space?
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
arr = sorted(nums)
n = len(arr)
i, j = (n - 1) >> 1, n - 1
for k in range(n):
if k % 2 == 0:
nums[k] = arr[i]
i -= 1
else:
nums[k] = arr[j]
j -= 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public void wiggleSort(int[] nums) {
int[] arr = nums.clone();
Arrays.sort(arr);
int n = nums.length;
int i = (n - 1) >> 1, j = n - 1;
for (int k = 0; k < n; ++k) {
if (k % 2 == 0) {
nums[k] = arr[i--];
} else {
nums[k] = arr[j--];
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> arr = nums;
sort(arr.begin(), arr.end());
int n = nums.size();
int i = (n - 1) >> 1, j = n - 1;
for (int k = 0; k < n; ++k) {
if (k % 2 == 0)
nums[k] = arr[i--];
else
nums[k] = arr[j--];
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func wiggleSort(nums []int) {
n := len(nums)
arr := make([]int, n)
copy(arr, nums)
sort.Ints(arr)
i, j := (n-1)>>1, n-1
for k := 0; k < n; k++ {
if k%2 == 0 {
nums[k] = arr[i]
i--
} else {
nums[k] = arr[j]
j--
}
}
}
|
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
| /**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var wiggleSort = function (nums) {
let bucket = new Array(5001).fill(0);
for (const v of nums) {
bucket[v]++;
}
const n = nums.length;
let j = 5000;
for (let i = 1; i < n; i += 2) {
while (bucket[j] == 0) {
--j;
}
nums[i] = j;
--bucket[j];
}
for (let i = 0; i < n; i += 2) {
while (bucket[j] == 0) {
--j;
}
nums[i] = j;
--bucket[j];
}
};
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
bucket = [0] * 5001
for v in nums:
bucket[v] += 1
n = len(nums)
j = 5000
for i in range(1, n, 2):
while bucket[j] == 0:
j -= 1
nums[i] = j
bucket[j] -= 1
for i in range(0, n, 2):
while bucket[j] == 0:
j -= 1
nums[i] = j
bucket[j] -= 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public void wiggleSort(int[] nums) {
int[] bucket = new int[5001];
for (int v : nums) {
++bucket[v];
}
int n = nums.length;
int j = 5000;
for (int i = 1; i < n; i += 2) {
while (bucket[j] == 0) {
--j;
}
nums[i] = j;
--bucket[j];
}
for (int i = 0; i < n; i += 2) {
while (bucket[j] == 0) {
--j;
}
nums[i] = j;
--bucket[j];
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> bucket(5001);
for (int& v : nums) ++bucket[v];
int n = nums.size();
int j = 5000;
for (int i = 1; i < n; i += 2) {
while (bucket[j] == 0) --j;
nums[i] = j;
--bucket[j];
}
for (int i = 0; i < n; i += 2) {
while (bucket[j] == 0) --j;
nums[i] = j;
--bucket[j];
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func wiggleSort(nums []int) {
bucket := make([]int, 5001)
for _, v := range nums {
bucket[v]++
}
n, j := len(nums), 5000
for i := 1; i < n; i += 2 {
for bucket[j] == 0 {
j--
}
nums[i] = j
bucket[j]--
}
for i := 0; i < n; i += 2 {
for bucket[j] == 0 {
j--
}
nums[i] = j
bucket[j]--
}
}
|
