## 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 * 104`
• `0 <= 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
}
``````
Copy The Code &

Input

cmd
nums = [1,5,1,1,6,4]

Output

cmd
[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]
}
``````
Copy The Code &

Input

cmd
nums = [1,5,1,1,6,4]

Output

cmd
[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)
``````
Copy The Code &

Input

cmd
nums = [1,3,2,2,3,1]

Output

cmd
[2,3,1,3,1,2]
Advertisements