Algorithm
Problem Name: 324. Wiggle Sort II
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
int cmp1(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
void msort(int *nums, int left, int right, int m) {
int i, j, k;
i = left;
j = right;
k = nums[i];
while (i < j) {
while (i < j && nums[j] >= k) {
j --; // find a number less than key from tail <-
}
if (i < j) {
nums[i] = nums[j]; // put this small number to the left
i ++;
}
while (i < j && nums[i] <= k) {
i ++; // find a number greater than key from head ->
}
if (i < j) {
nums[j] = nums[i]; // put this greater number to the right
j --;
}
}
nums[i] = k; // i is where key should be in
if (i > m) msort(nums, left, i - 1, m);
else if (i < m) msort(nums, i + 1, right, m);
}
void wiggleSort(int* nums, int numsSize) {
int i, m, k;
#if 1 // this is 56ms
int *tmp;
qsort(nums, numsSize, sizeof(int), cmp1); // no need to sort completely
tmp = malloc(numsSize * sizeof(int)); // O(n) memory
m = (numsSize + 1) / 2 ;
k = numsSize;
for (i = 0; i < numsSize; i ++) {
if (i % 2) tmp[i] = nums[-- k];
else tmp[i] = nums[-- m];
}
memcpy(nums, tmp, numsSize * sizeof(int));
free(tmp);
#else // this is 93ms :)
#define IDX(N) ((1 + 2 * (N)) % (numsSize | 1))
int r, c;
m = (numsSize - 1) / 2;
#if 1
msort(nums, 0, numsSize - 1, m);
#else
qsort(nums, numsSize, sizeof(int), cmp1); // no need to sort completely
#endif
k = nums[m]; // median number
//printf("%d\n", k);
i = m = 0; // left, current
r = numsSize - 1; // right
while (m < = r) {
c = nums[IDX(m)];
if (c > k) {
// swap left and current, advance left and current
nums[IDX(m)] = nums[IDX(i)];
nums[IDX(i)] = c;
i ++; m ++;
} else if (c < k) {
// swap current and right, reduce right
nums[IDX(m)] = nums[IDX(r)];
nums[IDX(r)] = c;
r --;
} else {
// advance current
m ++;
}
}
#endif
}
Input
nums = [1,5,1,1,6,4]
Output
[1,6,1,5,1,4]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const wiggleSort = function(nums) {
nums.sort((a, b) => a - b)
const ref = [...nums]
let j = nums.length - 1
for (let i = 1; i < nums.length; i += 2, j--) nums[i] = ref[j]
for (let i = 0; i < nums.length; i += 2, j--) nums[i] = ref[j]
}
Input
nums = [1,5,1,1,6,4]
Output
[1,6,1,5,1,4]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
heap = [-num for num in nums]
heapq.heapify(heap)
for i in range(1, len(nums), 2):
nums[i] = -heapq.heappop(heap)
for i in range(0, len(nums), 2):
nums[i] = -heapq.heappop(heap)
Input
nums = [1,3,2,2,3,1]
Output
[2,3,1,3,1,2]