@@ -0,0 +1,1925 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Given an unsorted array nums, reorder it in-place such that nums%5B0%5D %3C= nums%5B1%5D %3E= nums%5B2%5D %3C= nums%5B3%5D....%0A * %3Cp%3E%0A * For example, given nums = %5B3, 5, 2, 1, 6, 4%5D, one possible answer is %5B1, 6, 2, 5, 3, 4%5D.%0A * %3Cp%3E%0A * Company Tags: Google%0A * Tags: Array, Sort%0A * Similar Problems: (M) Sort Colors, (M) Wiggle Sort II%0A */%0Apublic class WiggleSort %7B%0A%0A    /**%0A     * The final sorted nums needs to satisfy two conditions:%0A     * %3Cp%3E%0A     * If i is odd, then nums%5Bi%5D %3E= nums%5Bi - 1%5D;%0A     * If i is even, then nums%5Bi%5D %3C= nums%5Bi - 1%5D.%0A     * %3Cp%3E%0A     * Proof: suppose if nums%5B0...i-1%5D is already wiggle.%0A     * If i is odd, then nums%5Bi - 2%5D %3E= nums%5Bi - 1%5D, nums%5Bi - 1%5D should %3C= nums%5Bi%5D%0A     * So if nums%5Bi - 1%5D %3E nums%5Bi%5D, swap them. And because nums%5Bi - 2%5D %3E= nums%5Bi - 1%5D, nums%5Bi - 2%5D %3E nums%5Bi%5D.%0A     * Then nums%5Bi - 2%5D %3E nums%5Bi%5D %3C nums%5Bi - 1%5D%0A     */%0A    public void wiggleSort(int%5B%5D nums) %7B%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            if ((i & 1) %3E 0) %7B%0A                if (nums%5Bi - 1%5D %3E nums%5Bi%5D) %7B%0A                    swap(nums, i);%0A                %7D%0A            %7D else if (i != 0 && nums%5Bi - 1%5D %3C nums%5Bi%5D) %7B%0A                swap(nums, i);%0A            %7D%0A        %7D%0A    %7D%0A%0A    private void swap(int%5B%5D nums, int i) %7B%0A        int temp = nums%5Bi%5D;%0A        nums%5Bi%5D = nums%5Bi - 1%5D;%0A        nums%5Bi - 1%5D = temp;%0A    %7D%0A%0A    /**%0A     * Same idea, just a more concise version.%0A     */%0A    public void wiggleSortB(int%5B%5D nums) %7B%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            int a = nums%5Bi - 1%5D;%0A            /*%0A             * When i is odd, left is true, and if nums%5Bi - 1%5D %3E nums%5Bi%5D, we need to swap%0A             * When i is even, left is false, and if nums%5Bi - 1%5D %3C nums%5Bi%5D, we need to swap%0A             */%0A            if ((i %25 2 == 1) == (a %3E nums%5Bi%5D)) %7B%0A                nums%5Bi - 1%5D = nums%5Bi%5D;%0A                nums%5Bi%5D = a;%0A            %7D%0A        %7D%0A    %7D%0A%0A%7D%0A

add Wiggle Sort