package leetcode;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/wiggle-sort-ii/
 */
public class Problem324 {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        boolean lessThan = true;
        int i = 0;
        int j = 1;
        while (j < nums.length) {
            if (lessThan) {
                if (nums[i] < nums[j]) {
                    i++;
                    swap(nums, i, j);
                    j = i + 1;
                    lessThan = false;
                } else {
                    j++;
                }
            } else {
                if (nums[i] > nums[j]) {
                    i++;
                    swap(nums, i, j);
                    j = i + 1;
                    lessThan = true;
                } else {
                    j++;
                }
            }
        }
        if (lessThan) {
            if (nums[i] > nums[j - 1]) {
                swap(nums, i, j - 1);
            }
        } else {
            if (nums[i] < nums[j - 1]) {
                swap(nums, i, j - 1);
            }
        }
        System.out.println("less than: " + lessThan);
        System.out.println(nums[i] + " -- " + nums[j-1]);
        // TODO:
    }

    private void swap(int[] nums, int i, int j) {
        if (i < nums.length && j < nums.length) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

    public static void main(String[] args) {
        Problem324 prob = new Problem324();

        int[] nums = new int[]{1, 5, 1, 1, 6, 4};
        prob.wiggleSort(nums);
        System.out.println(Arrays.toString(nums)); // [1, 4, 1, 5, 1, 6]

        nums = new int[]{1, 3, 2, 2, 3, 1};
        prob.wiggleSort(nums);
        System.out.println(Arrays.toString(nums)); // [2, 3, 1, 3, 1, 2]
    }
}

@@ -201,50 +201,44 @@
     
-boolean lessThan = true;%0A        int i = 0
+int%5B%5D newNums = new int%5Bnums.length%5D
 ;%0A  
@@ -247,77 +247,44 @@
     
+for (
 int 
-j = 1;%0A        while (j %3C nums.length) %7B%0A            if (lessThan
+i = 0; i %3C nums.length; i++
 ) %7B%0A
@@ -299,36 +299,29 @@
     
-    if (n
+newN
 ums%5Bi%5D 
-%3C
+=
  nums%5B
-j%5D) %7B
+i%5D;
 %0A   
@@ -329,196 +329,108 @@
     
-            i++;%0A                    swap(nums, i, j);%0A                    j = i + 1;%0A                    lessThan = false;%0A                %7D else %7B%0A                    j++;%0A      
+%7D%0A        int mid = nums.length / 2;%0A        if (nums.length %25 2 == 0) %7B%0A            mid--;%0A
         
   %7D%0A
@@ -417,34 +417,32 @@
  mid--;%0A        
-  
 %7D%0A            %7D 
@@ -439,85 +439,19 @@
     
-    %7D else %7B%0A                if (nums%5Bi%5D %3E nums%5Bj%5D) %7B%0A                    i++
+int j = mid
 ;%0A  
@@ -460,218 +460,47 @@
     
-            swap(nums, i, j);%0A                    j = i + 1;%0A                    lessThan = true;%0A                %7D else %7B%0A                    j++;%0A                %7D%0A            %7D%0A        %7D%0A        if (lessThan
+for (int i = 0; i %3C nums.length; i += 2
 ) %7B%0A
@@ -511,28 +511,24 @@
         
-if (
 nums%5Bi%5D 
 %3E nums%5Bj
@@ -523,307 +523,153 @@
 %5Bi%5D 
-%3E
+=
  n
+ewN
 ums%5B
-j - 1%5D) %7B%0A                swap(nums, i, j - 1);%0A            %7D%0A        %7D else %7B%0A            if (nums%5Bi%5D %3C nums%5Bj - 1%5D) %7B%0A                swap(nums, i, j - 1);%0A            %7D%0A        %7D%0A        System.out.println(%22less than: %22 + lessThan);%0A        System.out.println(nums%5Bi%5D + %22 -- %22 + n
+mid--%5D;%0A        %7D%0A        j = newNums.length - 1;%0A        for (int i = 1; i %3C nums.length; i += 2) %7B%0A            nums%5Bi%5D = newN
 ums%5Bj-
-1%5D)
+-%5D
 ;%0A  
@@ -678,16 +678,9 @@
     
-// TODO:
+%7D
 %0A   
@@ -891,407 +891,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem324 prob = new Problem324();%0A%0A        int%5B%5D nums = new int%5B%5D%7B1, 5, 1, 1, 6, 4%7D;%0A        prob.wiggleSort(nums);%0A        System.out.println(Arrays.toString(nums)); // %5B1, 4, 1, 5, 1, 6%5D%0A%0A        nums = new int%5B%5D%7B1, 3, 2, 2, 3, 1%7D;%0A        prob.wiggleSort(nums);%0A        System.out.println(Arrays.toString(nums)); // %5B2, 3, 1, 3, 1, 2%5D%0A    %7D
 %0A%7D%0A

Solve problem 324