Wiggle Sort

Wiggle Sort

要使得可以数组有如下顺序nums[0] <= nums[1] >= nums[2] <= nums[3]...

我们的做法是当index是奇数时如果num[i] < nums[i - 1]，那就两个数换一下；当index时偶数时如果nums[i] > nums[i - 1]，那就两个数换一下。这个算法的正确性证明：假设当前我们到了index i, 比如i是奇数，我们发现了nums[i] < nums[i - 1], 我们就换一下两个数。这个时候因为我们知道，nums[i -2]到一定是大于等于nums[i - 1]的，又因为nums[i] < nums[i - 1]，所以交换之后，nums[i - 2]一定是大于这个nums[i]的值的，所以这就保证了这个算法的正确性。

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }

        for (int i = 1; i < nums.length; i++) {
            if (i % 2 == 1 && nums[i] < nums[i - 1]) {
                swap(nums, i, i - 1);
            } else if (i % 2 == 0 && nums[i] > nums[i - 1]) {
                swap(nums, i, i - 1);
            }
        }
    }

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

Wiggle Sort II

这题的条件里取消了等于号，使得有duplicate存在的时候，会变得比较难处理。

discussion里这个帖子把思考过程说的比较清楚https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java/8。

首先用quickselect求一个median，然后在原数组上，放一个数值较小的那一半subarray的最大值，然后放一个数值较大的那一半subarray的最大值，不断重复这个步骤同时挪动指针，直到全部把数值赋完。vitural index这个解法我暂时还没搞懂，写先一个自己的解法。

• quickselect，parition中位数
• 3 way partition, target number是中位数，这样就可以把所有的中位数聚在一起了，这样分在了小的那一半但是数值等于中位数的数，一定是和最大的那几个数比较，因此不会出现前后两个值相等的情况。
• 时间复杂度O(n), 空间O(n)。

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }

        int[] temp = nums.clone();
        int medianIndex = nums.length % 2 == 1 ? nums.length / 2 : nums.length / 2 - 1;
        quickselect(temp, 0, temp.length - 1, medianIndex);

        int median = temp[medianIndex];
        threeWayPartition(temp, median);

        int left = medianIndex, right = nums.length - 1;
        int i = 0;
        while (left >= 0 && right > medianIndex) {
            if (i % 2 == 0) {
                nums[i++] = temp[left--];
            } else {
                nums[i++] = temp[right--];
            }
        }
        if (left >= 0) {
            nums[i++] = temp[left--];
        }
        if (right > medianIndex) {
            nums[i++] = temp[right--];
        }
    }

    private void quickselect(int[] nums, int start, int end, int k) {
        int left = start, right = end, pivot = nums[end];
        while (left < right) {
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            if (left < right) {
                swap(nums, left, right);
            }
        }
        swap(nums, left, end);

        if (left == k) {
            return;
        } else if (left < k) {
            quickselect(nums, left + 1, end, k);
        } else {
            quickselect(nums, start, left - 1, k);
        }
    }

    private void threeWayPartition(int[] nums, int target) {
        int left = 0, right = nums.length - 1, i = 0;
        while (i <= right) {
            if (nums[i] < target) {
                swap(nums, i, left);
                i++;
                left++;
            } else if (nums[i] == target) {
                i++;
            } else {
                swap(nums, i, right);
                right--;
            }
        }
    }

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

(G) Wiggle Sort变形

http://www.1point3acres.com/bbs/thread-146255-1-1.html

Q: 给两个数组，第一个数组用0和1组成，1表示升序，0表示降序，根据这个数组将第二个数组重新排列，让第二个数组符合第一个数组所表示的规律.

注意这题第一个数组元素的个数会比第二个少一个

例：
A = {0000} {11} {00} {1} {000}

B = {10 9 8 7 6} {5 4} {11 12} {3} {9 8 7}

其实Wiggle Sort就是这题的特殊形式，即A为10101010101010

这题的解法是对连续的Ai ~ Aj, 把Bi ~ Bj + 1排序即可。

代码实现sort部分偷懒了。

public class WiggleSort {
    public static void wiggleSort(int[] A, int[] B) {
        if (A.length + 1 != B.length) {
            return;
        }

        int i = 0;
        while (i < A.length) {
            int num = A[i];
            int j = i;
            while (j < A.length && A[j] == num) {
                j++;
            }
            if (num == 1) {
                Arrays.sort(B, i, j + 1);
            } else {
                Arrays.sort(B, i, j + 1);
                reverse(B, i, j);
            }
            i = j;
        }
    }

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;

            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        int[] A = {0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0};
        int[] B = {10, 9, 8, 7, 4, 5, 12, 11, 3, 9, 8, 7, 6};

        wiggleSort(A, B);

        for (int i = 0; i < B.length; i++) {
            System.out.print(B[i] + " ");
        }
    }
}