C++ solution with least exchange


  • 0
    S

    Keep "cur" for the active number to set to nums[i]. The key is for the group "nums[i-1] <= cur >= nums[i+1]", we satisfy "nums[i-1] <= cur" first, then if cur < nums[i+1], nums[i+1] must > nums[i-1], so after swap cur with nums[i+1], the first "nums[i-1] <= nums[i]" is still valid.

    class Solution {
    public:
        void wiggleSort(vector<int>& nums) {
            if (nums.size() < 2) return;
            
            int cur = nums[1];
            bool less = true;
            for (int i=1; i<=nums.size()-2; ++i) {
                if ((nums[i-1] > cur && less) || (nums[i-1] < cur && !less)) {
                    swap(nums[i-1], cur);
                }
                nums[i] = cur;
                cur = nums[i+1];
                less = !less;
            }
            
            nums[nums.size()-1] = cur;
         }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.