package code;

import java.util.Arrays;

/*
 * 324. Wiggle Sort II
 *  
 * Medium
 * Sort
 * 
 *       index map O(1)
 * Tips
 */
public class lc324 {
    public void wiggleSort(int[] nums) {
        if(nums.length==1) return;
        int n = nums.length, m = (n + 1) >> 1;// (nums.length+1)/2 +1
        int[] copy = Arrays.copyOf(nums, n);
        int median = findMedium(nums, 0, nums.length-1, m);

        for (int i = 0, j = 0, k = n - 1; j  median) {
                swap(copy, j, k--);
            } else {
                j++;
            }
        }

        for (int i = m - 1, j = 0; i >= 0; i--, j += 2) nums[j] = copy[i];  //i--bug
        for (int i = n - 1, j = 1; i >= m; i--, j += 2) nums[j] = copy[i];
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public int findMedium(int[] nums, int left, int right, int k){
        int l = left;
        int r = right;
        while(left