Simple C++ Solution, with explanation

  • 0

    Go through the array once and keep in mind whether we need the current element be larger or smaller than the previous one. If we need it to be larger yet it is actually smaller (or we need smaller but it is larger), swap them. Otherwise, proceed without any operation.

    It can be shown that the method above can always output a valid solution. The proof is left for you :P

    void wiggleSort(vector<int>& nums) {
        bool flag = false;
        for (int i = 1; i < nums.size(); i++) {
            if (flag ? (nums[i] >= nums[i - 1]) : (nums[i] <= nums[i - 1]))
                swap(nums[i], nums[i - 1]);
            flag = !flag;
        return ;

Log in to reply

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