|
| 1 | +// Source : https://leetcode.com/problems/wiggle-sort-ii/ |
| 2 | +// Author : Hao Chen |
| 3 | +// Date : 2017-01-02 |
| 4 | + |
| 5 | +/*************************************************************************************** |
| 6 | + * |
| 7 | + * Given an unsorted array nums, reorder it such that |
| 8 | + * nums[0] nums[2] . |
| 9 | + * |
| 10 | + * Example: |
| 11 | + * (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. |
| 12 | + * (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2]. |
| 13 | + * |
| 14 | + * Note: |
| 15 | + * You may assume all input has valid answer. |
| 16 | + * |
| 17 | + * Follow Up: |
| 18 | + * Can you do it in O(n) time and/or in-place with O(1) extra space? |
| 19 | + * |
| 20 | + * Credits:Special thanks to @dietpepsi for adding this problem and creating all test |
| 21 | + * cases. |
| 22 | + ***************************************************************************************/ |
| 23 | + |
| 24 | +classSolution { |
| 25 | + |
| 26 | +public: |
| 27 | +// |
| 28 | +// Solution - O(N*logN) |
| 29 | +// -------------------- |
| 30 | +// 1) Sorting the array with descending order |
| 31 | +// |
| 32 | +// 2) Split the sorted array into two parts, |
| 33 | +// and insert the 2nd half array into the 1st half array |
| 34 | +// |
| 35 | +// For example: [ 9 8 7 6 5 4 3 2 1 0 ] |
| 36 | +// |
| 37 | +// |
| 38 | +// 1st Large half: . 9 . 8 . 7 . 6 . 5 |
| 39 | +// 2nd Small half: 4 . 3 . 2 . 1 . 0 . |
| 40 | +// --------------------------------------- |
| 41 | +// Result: 4 9 3 8 2 7 1 6 0 5 |
| 42 | +// |
| 43 | +// Be careful if the length of array is odd number, |
| 44 | +// Such as: [5 4 3 2 1], |
| 45 | +// The 2nd half is [3 2 1] instead of [2 1] |
| 46 | +// |
| 47 | + |
| 48 | +voidwiggleSort01(vector<int>& nums) { |
| 49 | +sort(nums.begin(), nums.end(), [](int x,int y) {return x > y; }); |
| 50 | +int half = (nums.size() /2); |
| 51 | + |
| 52 | +for (int i=0; i<half; i++) { |
| 53 | +int v = nums[half+i]; |
| 54 | + nums.erase(nums.begin() + half + i ); |
| 55 | + nums.insert(nums.begin() + (2*i), v); |
| 56 | + } |
| 57 | + cout << endl; |
| 58 | + } |
| 59 | + |
| 60 | +// |
| 61 | +// After checked the discussion of Leetcode, I found there is a really brilliant idea |
| 62 | +// which used a tricky idea - virtual index. |
| 63 | +// |
| 64 | +// Please refer to the following link to see the full details: |
| 65 | +// https://discuss.leetcode.com/topic/32929/o-n-o-1-after-median-virtual-indexing |
| 66 | + |
| 67 | +voidwiggleSort02(vector<int>& nums) { |
| 68 | +int n = nums.size(); |
| 69 | + |
| 70 | +// Find a median. |
| 71 | +auto midptr = nums.begin() + n /2; |
| 72 | +nth_element(nums.begin(), midptr, nums.end()); |
| 73 | +int mid = *midptr; |
| 74 | + |
| 75 | +// Index-rewiring. |
| 76 | + #defineA(i) nums[(1+2*(i)) % (n|1)] |
| 77 | + |
| 78 | +// 3-way-partition-to-wiggly in O(n) time with O(1) space. |
| 79 | +int i =0, j =0, k = n -1; |
| 80 | +while (j <= k) { |
| 81 | +if (A(j) > mid) |
| 82 | +swap(A(i++),A(j++)); |
| 83 | +elseif (A(j) < mid) |
| 84 | +swap(A(j),A(k--)); |
| 85 | +else |
| 86 | + j++; |
| 87 | + } |
| 88 | + } |
| 89 | +voidwiggleSort(vector<int>& nums) { |
| 90 | +returnwiggleSort02(nums);//~140ms |
| 91 | +returnwiggleSort01(nums);//~230ms |
| 92 | + } |
| 93 | +}; |