1ms Java Solution with Clear Example


  • 2

    Use {1,3,6,9,8,2} as input data.
    Step 1: make each [even, odd] pair to be [small, large] --> {1,3,6,9,2,8}
    Step 2: make each [odd, even] pair to be [large, small] --> {1,6,3,9,2,8} Done!

    public void wiggleSort(int[] nums) {
        for (int i = 1; i < nums.length; i += 2)
            if (nums[i] < nums[i - 1]) swap(nums, i, i - 1);
        for (int i = 2; i < nums.length; i += 2)
            if (nums[i] > nums[i - 1]) swap(nums, i, i - 1);
    }
    
    public void swap(int[] a, int p, int q) {
        int t = a[p];
        a[p] = a[q];
        a[q] = t;
    }
    

    A fancy swap method like:

    public void swap(int[] a, int p, int q) {
        a[p] = a[p] + a[q];
        a[q] = a[p] - a[q];
        a[p] = a[p] - a[q];
    }

  • 0
    M

    very impressive !! can you explain why?


  • 0
    L
    This post is deleted!

  • 1
    L

    @MissYu
    I hope this would help you:
    Making [even, odd] pairs to be [small, large] will ensure the number before the odd index will be smaller than itself.
    Making [odd, even] pairs to be [large, small] will ensure the number after the odd index will be larger than itself.
    How to prove?
    Assume we have the following sequence after finishing the first round of exchange:
    [a1, a, b1, b, c1, c] here a1<a, b1<b, c1<c and this is guaranteed by the first switch.
    So, here we need to do the second switch for pairs [odd, even],
    Starting from [a, b1],
    if a>b1, we do not need to switch the element, continue to the next [odd, even] pair.
    if a<b1, we did the switch and make it become:
    [a1, b1, a, b, c1, c]
    here because a1<a, a<b1, so a1<b1. so we have a1<b1>a.
    And so forth.


Log in to reply
 

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