280. Wiggle Sort
Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
Quick to think of: O(nlogn)
public class Solution { public void wiggleSort(int[] nums) { Arrays.sort(nums); //sort the array, and then switch (1,2), (3,4), (5,6), ... for(int i = 2; i < nums.length; i+=2){ int tmp = nums[i-1]; nums[i-1] = nums[i]; nums[i] = tmp; } } }
O(n) solution:
class Solution { public void wiggleSort(int[] nums) { for (int i = 1; i < nums.length; i++) { if ((i % 2 == 1 && nums[i] < nums[i - 1]) || //for odd number, make sure nums[i] >= nums[i - 1] (i % 2 == 0 && nums[i] > nums[i - 1]) //for even number, make sure nums[i] <= nums[i - 1] ) { int tmp = nums[i - 1]; nums[i - 1] = nums[i]; nums[i] = tmp; } } } }
324. Wiggle Sort II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?
public class Solution { public void wiggleSort(int[] nums) { Arrays.sort(nums); int[] copy = new int[nums.length]; for(int i = 0; i< nums.length; ++i) { copy[i] = nums[i]; } for(int i = 0; i< nums.length; ++i) { int w = i%2; if(w == 0)//Take 2, 1, 0 nums[i] = copy[(nums.length-1)/2 - i/2]; else //Take 5, 4, 3 nums[i] = copy[nums.length-1 - i/2]; } //Take in this order to avoid the case: [4,5,5,6] } }
Thought based on https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java
1. Split the array by medians, into smalls, medians, larges.
2. Get the output
2.1 Use the smalls to fill even spots from right to left.
2.2 Use the larges to fill odd spots from left to right.
2.3 Leave the medians at two ends.
Original Array {6,13,5,4,5,2}. Move largers to the left and smalls to the right.
13 6 5 5 4 2
MIndex : 0 1 2 3 4 5 Small half: M S S Large half: L L Mprivate int mappingFunction(int index, int n) {
//example for this mapping
//n = 6, n|1 = 7
//Original idx: 0 1 2 3 4 5
//Mapped idx: 1 3 5 0 2 4
return (1 + 2 * index) % (n | 1);
}
Here is solutino based on 215. Kth Largest Element in an Array.
And the sorting part is similar to 75. Sort colors below. See its description.
class Solution { public void wiggleSort(int[] nums) { int median = findKthLargest(nums, (nums.length + 1) / 2); int n = nums.length; int left = 0, i = 0, right = n - 1; while (i <= right) { int mappedIndex = newIndex(i, n); //Iterate through 1,3,5,7,0,2,4,6,8... int current = nums[mappedIndex]; /** * move current number based on its value, deciding whether it should go to a * larger-than median position, or a smaller-than median position. * * Next larger-than median position is denoted by newIndex[Left] * Next smaller-than median position is denoted by newIndex[Right] */ if (current > median) { swap(nums, newIndex(left, n), mappedIndex); ++left; ++i; } else if (current < median) { swap(nums, newIndex(right, n), mappedIndex); --right; } else ++i; } } private int newIndex(int index, int n) { /** example for this mapping * n = 6, n|1 = 7 * Original idx: 0 1 2 3 4 5 * Mapped idx: 1 3 5 0 2 4 */ return (1 + 2 * index) % (n | 1); } private int findKthLargest(int[] a, int k) { int n = a.length; int p = quickSelect(a, 0, n - 1, n - k + 1); return a[p]; } private int quickSelect(int[] a, int lo, int hi, int k) { int i = lo, j = hi, pivot = a[hi]; while (i < j) { if (a[i++] > pivot) swap(a, --i, --j); } swap(a, i, hi); int m = i - lo + 1; if (m == k) return i; else if (m > k) return quickSelect(a, lo, i - 1, k); else return quickSelect(a, i + 1, hi, k - m); } private void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } }
75. Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?
public class Solution { public void sortColors(int[] nums) { int pleft = 0; int p = 0; int pright = nums.length-1; while(p<=pright){ if(nums[p] == 0) swap(nums, pleft++, p++); else if(nums[p] == 1) ++p; else //if(nums[p] == 2) swap(nums, p, pright--); } } private void swap(int[] nums, int a, int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }