Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- vector<int> rearrangeArray(vector<int>& nums) {
- sort(nums.begin(), nums.end());
- int n=nums.size();
- vector<int> res(n, 0);
- int i = 0;
- for(int nn:nums){
- res[i] = nn;
- i += 2;
- if(i>=n)
- i=1;
- }
- return res;
- }
- };
- -----------------------
- vector<int> rearrangeArray(vector<int>& A) {
- sort(A.begin(), A.end());
- for (int i = 1; i < A.size(); i += 2)
- swap(A[i], A[i - 1]);
- return A;
- }
- -----------------------
- vector<int> rearrangeArray(vector<int>& nums) {
- int n = nums.size();
- // Find a median.
- auto midptr = nums.begin() + n / 2;
- nth_element(nums.begin(), midptr, nums.end());
- int mid = *midptr;
- // Index-rewiring.
- #define A(i) nums[(1+2*(i)) % (n|1)]
- // 3-way-partition-to-wiggly in O(n) time with O(1) space.
- int i = 0, j = 0, k = n - 1;
- while (j <= k) {
- if (A(j) > mid)
- swap(A(i++), A(j++));
- else if (A(j) < mid)
- swap(A(j), A(k--));
- else
- j++;
- }
- return nums;
- }
- -----------------------
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement