# Question

Formatted question description: https://leetcode.ca/all/324.html

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.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

# Algorithm

Sort the array first, and then make adjustments.

The adjustment method is to find the number in the middle of the array, which is equivalent to dividing the ordered array into two parts from the middle.

Then take one from the end of the first half, and go one from the end of the second half, so that the first number is less than the second number.

Then take the second to last from the first half and take the second to last from the second half. This ensures that the second number is greater than the third number and the third number is less than the fourth number.

And so on until all of them are processed.

# Code

• import java.util.Arrays;

public class Wiggle_Sort_II {

public static void main(String[] args) {
Wiggle_Sort_II out = new Wiggle_Sort_II();
Solution_NlogN s = out.new Solution_NlogN();

s.wiggleSort(new int[]{1, 5, 1, 1, 6, 4});
}

// test: [1,5,1,1,6,4]
// result: [1,6,1,5,1,4]
class Solution_NlogN {
public void wiggleSort(int[] nums) {

if (nums == null || nums.length <= 1) {
return;
}

Arrays.sort(nums);

int[] temp = new int[nums.length];

int left = (nums.length - 1) / 2;
int right = nums.length - 1;
// int p = temp.length - 1; // @note: NOT from end index to 0, to avoid tie situation
int p = 0;

// while (p >= 0) {
while (p < temp.length) {
// if (nums[p] % 2 == 0) {
if (p % 2 == 0) {
temp[p++] = nums[left--];
} else {
temp[p++] = nums[right--];
}
}

System.arraycopy(temp, 0, nums, 0, nums.length);
} // 1,1,1,4,5,6 // 4,5,5,6
}

// divide and conquer
public class Solution_oN {
public void wiggleSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}

int n = nums.length;

// Step 1: Find median of the array, return the index of the median
int median = findMedian(nums, 0, n - 1, (n - 1) / 2);

// Step 2: 3-way sort, put median in the middle,
// numbers less than median on the left,
// numbers greater than median on the right
int[] temp = new int[n];
int left = 0;
int right = n - 1;

for (int i = 0; i < n; i++) {
if (nums[i] < nums[median]) {
temp[left] = nums[i];
left++;
} else if (nums[i] > nums[median]) {
temp[right] = nums[i];
right--;
}
}

// add median into the middle
for (int i = left; i <= right; i++) {
temp[i] = nums[median];
}

// Step 3: wiggle sort
left = (n - 1) / 2;
right = n - 1;

for (int i = 0; i < n; i++) {
if ((i & 1) == 0) {
nums[i] = temp[left];
left--;
} else {
nums[i] = temp[right];
right--;
}
}
}

private int findMedian(int[] nums, int lo, int hi, int k) {
if (lo >= hi) {
return lo;
}

int pivot = partition(nums, lo, hi);
if (pivot == k) {
return pivot;
}

if (pivot > k) {
return findMedian(nums, lo, pivot - 1, k);
} else {
return findMedian(nums, pivot + 1, hi, k);
}
}

// first half is larger than pivot-value
private int partition(int[] nums, int lo, int hi) {
int pivot = nums[lo];
int i = lo + 1;
int j = hi;

while (i <= j) {
while (i <= j && nums[i] < pivot) {
i++;
}

while (i <= j && nums[j] >= pivot) {
j--;
}

if (i <= j) {
swap(nums, i, j);
}
}

swap(nums, lo, j);

return j;
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}

############

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--];
}
}
}
}

• // O(n) space
class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> tmp = nums;
int n = nums.size(), k = (n + 1) / 2, j = n;
sort(tmp.begin(), tmp.end());
for (int i = 0; i < n; ++i) {
nums[i] = i & 1 ? tmp[--j] : tmp[--k];
}
}
};

• '''
>>> nums = list(range(1,11))
>>> nums
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> nums[::2]
[1, 3, 5, 7, 9]
>>> nums[1::2]
[2, 4, 6, 8, 10]
>>>
>>> mid = (len(nums) - 1) // 2
>>> mid
4
>>> nums[mid::-1]
[5, 4, 3, 2, 1]
>>> nums[:mid:-1]
[10, 9, 8, 7, 6]
>>>
>>> nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1]
>>> nums
[5, 10, 4, 9, 3, 8, 2, 7, 1, 6]
>>>
'''
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
nums.sort()
mid = (n - 1) // 2
nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1]

# better to have descending list, below having error
#   input: [4,5,5,6], below line output: [4,5,5,6]
# nums[::2], nums[1::2] = nums[:mid+1:1], nums[mid+1::1]
'''
>>> nums=[4,5,5,6]
>>> mid = (len(nums) - 1) // 2
>>>
>>> nums[::2]
[4, 5]
>>> nums[1::2]
[5, 6]
>>> nums[mid::-1]
[5, 4]
>>> nums[:mid:-1]
[6, 5]
>>> nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1]
>>> nums
[5, 6, 4, 5]
'''
class Solution: # extra space
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
arr = sorted(nums) # extra O(N) space
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

class Solution: # quicksort, without full sort
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
if n <= 1:
return

mid = self.findKthLargest(nums, (n + 1) // 2)

def idx(i):
return (2 * i + 1) % (n | 1)

i, j, k = 0, 0, n - 1
while j <= k:
if nums[idx(j)] > mid:
nums[idx(i)], nums[idx(j)] = nums[idx(j)], nums[idx(i)]
i += 1
j += 1
elif nums[idx(j)] < mid:
nums[idx(j)], nums[idx(k)] = nums[idx(k)], nums[idx(j)]
k -= 1
else:
j += 1

def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
left, right = 0, n - 1

while True:
pivotIdx = self.partition(nums, left, right)
if pivotIdx == k - 1:
return nums[pivotIdx]
elif pivotIdx < k - 1:
left = pivotIdx + 1
else:
right = pivotIdx - 1

def partition(self, nums, left, right):
pivot = nums[left]
l, r = left + 1, right

while l <= r:
if nums[l] < pivot and nums[r] > pivot:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
elif nums[l] >= pivot:
l += 1
else:
r -= 1

nums[left], nums[r] = nums[r], nums[left]
return r


• 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--
}
}
}

• /**
* @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];
}
};