324. Wiggle Sort II

这题居然没记过。

刷 June-12-2019

wiggle sort I
比较直观就是一大一小

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums.length <= 1) return;
        
        boolean findLarger = true;
        for (int i = 1; i < nums.length; i ++) {
            if (findLarger) {
                if (nums[i] < nums[i - 1]) {
                    swap(i, i - 1, nums);
                }
            } else {
                if (nums[i] > nums[i - 1]) {
                    swap(i, i - 1, nums);
                }
            }
            findLarger = !findLarger;
        }
        return;
    }
    
    public void swap(int l, int r, int[] nums) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}

然后看亩地有人说G家的面试题是A数组给单调性，B数组根据A的来调。
A = [1,1,1,1][0,0,0][1,1][0,0,0]
给个数组，1代表递增，0代表递减，B数组来根据A的递增递减排列。
B = [9,8,7,6][19,21,66][12,3][11,5,28]

先排列[1,1,1,1] 要带上=> [6,7,8,9]
再排列[1,1,1,1][0,0,0] => 要带上上一个区间的最后一个元素 => [6,7,8,66][21,19,9]
再排列[1,1,1,1][0,0,0][1,1] => [6,7,8,66][21,19,3][9,12]
…
Wiggle sort-I其实就是A数组是[1][0][1][0]这样，每次temp都是带上i-1来比较的。

Wiggle sort II
一个意思，只不过多了相等的元素。只会最单纯的解。 找中位数，然后奇偶位从左边右边来回拿。
要倒着拿，否则[1,2,2,3] 会挂，得是[****2,3,1,2]，目的是左边最大值尽量远离右边最小值来避免多个相等中位数。
中位数要当做左边最大值对待，所以
m = (nums.length + 1) >> 1 - 1
m = (nums.length + 1)/2 -1;

    public void wiggleSort(int[] nums) {
        if (nums.length <= 1) return;
        Arrays.sort(nums);
        int[] tempNums = new int[nums.length];
        
        int s = ((nums.length + 1) >> 1) - 1;
        int l = nums.length - 1;
        
        for (int i = 0; i < nums.length; i ++) {
            tempNums[i] = (i & 1) == 0 ? nums[s--] : nums[l --];
        }
        
        for (int i = 0; i < nums.length; i ++) {
            nums[i] = tempNums[i];
        }
    }