leetcode 324. Wiggle Sort II-蒲公英云

leetcode 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?

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        if(nums.empty())
            return;
        vector<int>aa=nums;
        sort(aa.begin(),aa.end());
        if(nums.size()%2!=0)
            for(int i=0;i<aa.size();)
            {
                nums[i]=aa[i/2];
                if(i+1<aa.size())
                    nums[i+1]=aa[nums.size()/2+i/2+1];
                i+=2;
            }
        else
        {
            for(int i=0;i<aa.size();)
            {
                nums[i]=aa[i/2];
                if(i+1<aa.size())
                {
                    nums[i+1]=aa[nums.size()/2+i/2];
                }
                i+=2;
            }
        }
        for(int i=2;i<nums.size()-1;)
        {
            if(nums[i-1]<=nums[i])
            {
                int tp=nums[i+1];
                nums[i+1]=nums[i-1];
                nums[i-1]=tp;
                i=2;
            }
            else if(nums[i+1]<=nums[i])
            {
                int tp=nums[i];
                nums[i]=nums[i-2];
                nums[i-2]=tp;
                i=2;
            }
            else
                i+=2;
        }
    }
};