nikunjsoni

324

Jun 28th, 2021
108
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. O(nlogn) time, O(1) space
  2.  
  3. class Solution {
  4. public:
  5.     void wiggleSort(vector<int>& nums) {
  6.         vector<int> sorted(nums);
  7.         sort(sorted.rbegin(), sorted.rend());
  8.         int n = nums.size(), m = n | 1;
  9.         for(int i=0; i<n; i++)
  10.             nums[(1+2*i)%m] = sorted[i];
  11.     }
  12. };
  13.  
  14. ---------------
  15. O(n) time, O(1) space
  16.  
  17. class Solution {
  18. public:
  19.     void wiggleSort(vector<int>& nums) {
  20.         if (nums.empty()) {
  21.             return;
  22.         }    
  23.         int n = nums.size();
  24.        
  25.         // Step 1: Find the median         
  26.         vector<int>::iterator nth = next(nums.begin(), n / 2);
  27.         nth_element(nums.begin(), nth, nums.end());
  28.         int median = *nth;
  29.  
  30.         // Step 2: Tripartie partition within O(n)-time & O(1)-space.          
  31.         auto m = [n](int idx) { return (2 * idx + 1) % (n | 1); };         
  32.         int first = 0, mid = 0, last = n - 1;
  33.         while (mid <= last) {
  34.             if (nums[m(mid)] > median) {
  35.                 swap(nums[m(first)], nums[m(mid)]);
  36.                 ++first;
  37.                 ++mid;
  38.             }
  39.             else if (nums[m(mid)] < median) {
  40.                 swap(nums[m(mid)], nums[m(last)]);
  41.                 --last;
  42.             }              
  43.             else {
  44.                 ++mid;
  45.             }
  46.         }
  47.     }    
  48. };
  49.  
RAW Paste Data