nikunjsoni

1968

Aug 15th, 2021
884
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<int> rearrangeArray(vector<int>& nums) {
  4.         sort(nums.begin(), nums.end());
  5.         int n=nums.size();
  6.         vector<int> res(n, 0);
  7.         int i = 0;
  8.         for(int nn:nums){
  9.             res[i] = nn;
  10.             i += 2;
  11.             if(i>=n)
  12.                 i=1;
  13.         }
  14.         return res;
  15.     }
  16. };
  17. -----------------------
  18.  
  19.     vector<int> rearrangeArray(vector<int>& A) {
  20.         sort(A.begin(), A.end());
  21.         for (int i = 1; i < A.size(); i += 2)
  22.             swap(A[i], A[i - 1]);
  23.         return A;
  24.     }
  25.  
  26. -----------------------
  27.  
  28. vector<int> rearrangeArray(vector<int>& nums) {
  29.         int n = nums.size();
  30.  
  31.         // Find a median.
  32.         auto midptr = nums.begin() + n / 2;
  33.         nth_element(nums.begin(), midptr, nums.end());
  34.         int mid = *midptr;
  35.  
  36.         // Index-rewiring.
  37.         #define A(i) nums[(1+2*(i)) % (n|1)]
  38.  
  39.         // 3-way-partition-to-wiggly in O(n) time with O(1) space.
  40.         int i = 0, j = 0, k = n - 1;
  41.         while (j <= k) {
  42.             if (A(j) > mid)
  43.                 swap(A(i++), A(j++));
  44.             else if (A(j) < mid)
  45.                 swap(A(j), A(k--));
  46.             else
  47.                 j++;
  48.         }
  49.         return nums;
  50.     }
  51. -----------------------
RAW Paste Data