Dare2Solve
The task is to reorder an unsorted array nums
such that nums[0] < nums[1] > nums[2] < nums[3]...
(this is known as wiggle sort). This means that the elements at even indices should be less than their neighboring odd indices, and elements at odd indices should be greater than their neighbors.
By sorting the array, we can easily place smaller numbers in the even positions and larger numbers in the odd positions. This ensures that the wiggle property is satisfied: numbers at odd positions are greater than their neighbors and numbers at even positions are smaller. The key is to rearrange the array by alternating between the two halves of the sorted array.
nums
array by alternately taking elements from the left and right halves of the sorted array.n
is the number of elements.nums
, which takes (O(n)) space.class Solution {
public:
void wiggleSort(std::vector<int>& nums) {
std::vector<int> sorted(nums);
std::sort(sorted.begin(), sorted.end());
int mid = (nums.size() + 1) / 2;
int j = mid - 1;
int k = nums.size() - 1;
for (int i = 0; i < nums.size(); i++) {
if (i % 2 == 0) {
nums[i] = sorted[j--];
} else {
nums[i] = sorted[k--];
}
}
}
};
class Solution:
def wiggleSort(self, nums):
sorted_nums = sorted(nums)
mid = (len(nums) + 1) // 2
j, k = mid - 1, len(nums) - 1
for i in range(len(nums)):
if i % 2 == 0:
nums[i] = sorted_nums[j]
j -= 1
else:
nums[i] = sorted_nums[k]
k -= 1
class Solution {
public void wiggleSort(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
int mid = (nums.length + 1) / 2;
int j = mid - 1;
int k = nums.length - 1;
for (int i = 0; i < nums.length; i++) {
if (i % 2 == 0) {
nums[i] = sorted[j--];
} else {
nums[i] = sorted[k--];
}
}
}
}
var wiggleSort = function (nums) {
nums.sort((a, b) => a - b);
let sorted = nums.slice();
let mid = Math.floor((nums.length + 1) / 2);
let j = mid - 1;
let k = nums.length - 1;
for (let i = 0; i < nums.length; i++) {
if (i % 2 === 0) {
nums[i] = sorted[j--];
} else {
nums[i] = sorted[k--];
}
}
};