324. Wiggle Sort II
Approach
Find the virtual median via quickselect, then use 3-way Dutch-Flag
partition with index mapping to place larger elements at odd positions.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
The two-pointer technique places pointers at different positions (often the two ends) and moves them toward each other. It turns O(n²) nested loops into O(n) sweeps for problems like pair sums, removing duplicates, and container capacity. Works best on sorted or partitioned arrays.
Divide and conquer splits a problem into independent sub-problems, solves each recursively, and combines the results. Classic examples: merge sort, quick sort, binary search, and closest pair of points. Master Theorem helps analyze time complexity: T(n) = aT(n/b) + f(n).
// Approach: Find the virtual median via quickselect, then use 3-way Dutch-Flag
// partition with index mapping to place larger elements at odd positions.
// Time: O(n) avg Space: O(1)
public class Solution
{
public void WiggleSort(int[] nums)
{
int n = nums.Length;
int median = FindKthLargest(nums, (n + 1) / 2);
for (int i = 0, j = 0, k = n - 1; i <= k;)
{
if (nums[A(i, n)] > median)
Swap(nums, A(i++, n), A(j++, n));
else if (nums[A(i, n)] < median)
Swap(nums, A(i, n), A(k--, n));
else
++i;
}
}
private int A(int i, int n)
{
return (1 + 2 * i) % (n | 1);
}
private int FindKthLargest(int[] nums, int k)
{
return QuickSelect(nums, 0, nums.Length - 1, k);
}
private int QuickSelect(int[] nums, int l, int r, int k)
{
int pivot = nums[r];
int nextSwapped = l;
for (int i = l; i < r; ++i)
{
if (nums[i] >= pivot)
Swap(nums, nextSwapped++, i);
}
Swap(nums, nextSwapped, r);
int count = nextSwapped - l + 1; // the number of `nums` >= pivot
if (count == k)
return nums[nextSwapped];
if (count > k)
return QuickSelect(nums, l, nextSwapped - 1, k);
return QuickSelect(nums, nextSwapped + 1, r, k - count);
}
private void Swap(int[] nums, int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}