WiggleSort [source code]

public class WiggleSort {
static
/******************************************************************************/
public class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 1 && i + 1 < n && nums[i] < nums[i + 1])
                swap(nums, i, i + 1);
            else if (i % 2 == 0 && i + 1 < n && nums[i] > nums[i + 1])
                swap(nums, i, i + 1);
        }
    }

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

    public static void main(String[] args) {
        WiggleSort.Solution tester = new WiggleSort.Solution();
        int[][] inputs = {
            {3, 5, 2, 1, 6, 4}
        };
        for (int i = 0; i < inputs.length; i++) {
            int[] nums = inputs[i];
            String original = Printer.array(nums);
            tester.wiggleSort(nums);
            String output = Printer.array(nums);
            System.out.println(Printer.seperator());
            System.out.println(Printer.wrapColor(original, "magenta") + " -> " + Printer.wrapColor(output, verify(nums) ? "green" : "red"));
        }
    }

    public static boolean verify(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0 && i + 1 < nums.length && nums[i] > nums[i + 1])
                return false;
            else if (i % 2 == 1 && i + 1 < nums.length && nums[i] < nums[i + 1])
                return false;
        }
        return true;
    }
}

看了例子之后, 想到的第一个算法就是直接sort了之后, 对折一下, 间隔插值. 不过这样最后的时间是O(NlgN). 看了一眼discussion首页, 最优解是O(N)的, 所以先想想看能不能做出来这个;

这个速度不够快, 可能是因为我是一个先sort, 然后处理啥的思路, 这种思路经常很大的一个问题就是overkill; 注意看这个题目里面的用词: one possible, 所以其实这个最后wiggle sort之后是可以有很多结果了, 也就是说这个wiggle sort其实是一个不完全的sort, 所以才可以做到O(N), 因为并没有做到一个真正的sorting;

这个题目想了半天还是想不出来O(N)的解, 只好看答案了;

上面的答案是editorial3; 其实我也挺靠近这个答案, 不过我感觉我目前比较欠缺的一个问题就是一个看透问题本质的能力, 也就是看透问题, 然后相处一个heuristic的能力, 而不是代码上面写算法的问题(就算是比较复杂的代码, 我其实也能写个三五不离十); 但是看透问题本质, 比如之前的counting问题, 我就没有做到看透本质;

这个问题的本质其实也是非常简单: 从visual的角度来看(sorting要多利用visual, 这个其实以前也是讲过一次的. 我在思考这个问题的时候再一次陷入了历史信息流的窠臼当中, 就想着怎样存取历史信息来完成合理的操作), 这个问题最后想要做到的其实就是上下交替的锯齿形状;

这个问题其实给出的这个例子也是挺姜的, 故意用这么一个例子来诱导你往sorting上面去想. 实际上这个问题跟sorting的关系相当不大; visual是可以帮助你理解这个问题的本质的; 只要你看清楚这个问题最后想要deliver的其实就是relative order between adjacent entries的话, 这个问题就很简单了;

另外array问题里面, swap好像也是一个常规了; 要有对这些常规熟悉的习惯, 这样在该想起的时候才能想的起来;
谈起一个topic, 有哪些常见的操作, 脑子里可以稍微快速的过一下;

这个东西感觉后期可以适当总结一下; 就跟以前高中做数学题一样, 一个题型来了, 脑子里应该立刻闪过一个list, 哪些常用的操作和套路, 都得有. 这样才能避免该想起来的时候想不起来;

看清了之后, 这个问题就不难做了; 最后的速度是1ms (67%), 最优解;

现在对于我这种无法看清问题本质的问题很担心, 只能寄希望于, 以后题目见的多了, 那么需要完成的objective见多了(比如这里的objective就是一个锯齿形的visual, 或者上升下降交替的trend)之后会更熟练一些;

本来的想法其实还是自己简单一个例子做做看的, 不过就算是拿到了这里题目给的这个例子, 还是没有理解究竟怎样做, 因为这个问题的一个点在于, 最后possible的答案其实是无限多的, 你最后希望达到的只是一个要求. 所以就算是那这个例子在手上, 也有一种不知道下面该干什么的意思;

不过这个题目本身对于问题的描述可能也是一个线索? 比如你怎么理解题目本身描述的feature; 这里题目给出的feature就是相邻的entry之间的大小relative order.

感觉我拘泥于历史信息流算法然后想不到一个更简单的正确思路已经发生过不止一次了; 有时候要适时止损的, 看到历史信息流这个思路不行了, 就可以考虑想想是不是没有这么复杂(当然我当时看到历史信息流做不出来的时候, 想到的更多的是: 也许我设计的这个历史信息流还不够聪明, 也需有什么很slick的小trick能让everything suddenly make sense);

另外其实这个题目也是有一个类似历史信息流的写法的:

public void wiggleSort(int[] nums) {  
    boolean less = true;  
    for (int i = 0; i < nums.length - 1; i++) {  
        if (less) {  
            if (nums[i] > nums[i + 1]) {  
                swap(nums, i, i + 1);  
            }  
        } else {  
            if (nums[i] < nums[i + 1]) {  
                swap(nums, i, i + 1);  
            }  
        }  
        less = !less;  
    }  
}

不过更多的是属于类似分段算法; 这里其实根本没有利用什么历史信息, less代表的其实就是当前的i和i+1之间应该是less than or not的一个requirement, 所以不算历史信息; 至于相邻entry的access也更加算不上历史信息了;

另外这里是editorial上面原来的代码:

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

以及一个stefan优化了一下的代码:

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

这个人的逻辑简化能力还是挺强的;

另外这个问题有一个小的抉择点: 你在i的时候,到底是跟前面比还是跟后面比? 其实是无所谓的, 奇数位置的要大于前后, 偶数位置的要小于前后, 这个你站在i, 只要统一是往一个方向比的就行了;

2018-04-23 00:55:46 回头来看这个算法, 当时可能想证明想了半天, 实际上想想证明也不是很难, 这题很明显需要一个induction的角度去证明; 你就从最开始的base case开始看, 比如1处理完了之后, [0] <= [1]肯定成立; 然后你要比较[1]和[2], 如果说[1] <= [2], 我们就swap他们, 这个是不会破坏[0]和[1]的关系的; 因为你把更大的[2]给扔过去做了[0]的上家, 所以上一个edge完全不会被破坏; 进一步的; 当你在处理[i]和[i+1]的时候, 唯一可能被印象的就是[i-1]和[i]之间的关系; 但是类似的证明应该可以证明不会有影响;

虽然这样说, 这个算法我个人认为还是挺难想的, 属于那种闭着眼睛先猜, 猜对了再证明的题目, 这种我是最害怕的; 当然这个猜的过程, 其实可以美其名曰greedy; 说的好像在找的时候也是有目的的寻找一样了;

I have to say nobody explains the sufficiency of the following algo:

The final sorted nums needs to satisfy two conditions:

If i is odd, then nums[i] >= nums[i - 1];

If i is even, then nums[i] <= nums[i - 1].

The code is just to fix the orderings of nums that do not satisfy 1
and 2.

这个是discussion上面一个家伙尝试理论上证明这个算法的correctness, 其实没有什么好证明的, 自己用visual来演示一下就行了: 比如i是奇数, 我们要保证[i] >= [i + 1], 那么我们在i这一步完成了这个操作. 问题在于, i + 1及以后的操作是否会让[i+1]重新变得超过[i]? visual一下就知道不可能. 如果[i+1] and [i+2]不交换, 那么i位置的这个trend就保持了; 如果被交换了, 唯一的可能的原因就是[i+2] < [i+1], 自然[i+2] < [i], 所以在i的trend还是保持正确了. 这个东西并不难证明;

不过这样一个思考也展示了, 这个算法并不是我想想的那么trivial;

这个问题最好的算法基本就是这个了, discussion没有更好的算法了;

Problem Description

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

Difficulty:Medium
Total Accepted:28.7K
Total Submissions:50.6K
Contributor: LeetCode
Companies
google
Related Topics
array sort
Similar Questions
Sort Colors Wiggle Sort II