324. Wiggle Sort II - cocoder39/coco39_LC GitHub Wiki
A hard follow up of wiggle sort where the reorder rule doesn't allow identical neighbors.
Method 1: T = O(N * lg N) and S = O(N)
Main idea is sorting the array, then divide the sorted array into two halves (called small and large). Write small half into odd index and large half into even index.
Small half: 4 . 3 . 2 . 1 . 0 .
Large half: . 9 . 8 . 7 . 6 . 5
Together: 4 9 3 8 2 7 1 6 0 5
Proof:
Small half: s4 . s3 . s2 . s1 . s0 .
Large half: . l4 . l3 . l2 . l1 . l0
Together: s4 l4 s3 l3 s2 l2 s1 l1 s0 l0
it is guaranteed that l[i] >= s[i] >= s[i - 1] but l[i] = s[i] is not allowed. How to prove l[i] > s[i]?
Think about following problem first, given a sequence of 4 red balls, how many blue ball can you insert into the sequence such that no two blue balls are neighbors? Answer is 5.
if l[i] == s[i], then l[i] == l[i - 1] ... == l[0] == s[small.size() - 1] == s[small.size - 2] ... == s[i]. small.size + 1 identical elements in total, thus no possible solution for this problem.
void wiggleSort(vector<int>& nums) {
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
int large = nums.size() - 1;
int small = large / 2;
for (int i = 0; i < nums.size(); i++) {
if (i % 2)
nums[i] = sorted[large--];
else
nums[i] = sorted[small--];
}
}
Method 2: average time is O(n), O(1) memory
average time of nth_element() is O(n), memory is not sure. We can achieve O(n) average time and O(1) memory through 215. Kth Largest Element in an Array. we find out the median of nums, then partition nums into three parts, one is less than median, one is equal to median, the rest is larger than median. we then rearrange nums like M L S L S L S M. using an O(n) aux array can help us achieve our goal.
we can play a tricky here to achieve O(1) memory. which is `#define map(i) nums[(1 + 2 * (i)) % (sz | 1)], The partition is almost same as 75. Sort Colors, except here larger part is in the left.
Accessing A(0) actually accesses nums[1].
Accessing A(1) actually accesses nums[3].
Accessing A(2) actually accesses nums[5].
Accessing A(3) actually accesses nums[7].
Accessing A(4) actually accesses nums[9].
Accessing A(5) actually accesses nums[0].
Accessing A(6) actually accesses nums[2].
Accessing A(7) actually accesses nums[4].
Accessing A(8) actually accesses nums[6].
Accessing A(9) actually accesses nums[8].
void wiggleSort(vector<int>& nums) {
int sz = nums.size();
auto it_mid = nums.begin() + sz / 2;
nth_element(nums.begin(), it_mid, nums.end());
int mid = *it_mid;
#define map(i) nums[(1 + 2 * (i)) % (sz | 1)]
//three way partition
//larger first, then mid, then smaller
int gt = 0, lt = sz - 1;
int i = 0;
while (i <= lt) {
if (map(i) > mid) {
swap(map(i++), map(gt++));
}
else if (map(i) < mid) {
swap(map(i), map(lt--));
}
else {
i++;
}
}
}