边工作边刷题：70天一遍leetcode: day 45-2

Wiggle Sort II

要点：这题就是关于如何按序插入，基本的logic这个帖子介绍的很清楚：https://leetcode.com/discuss/76965/3-lines-python-with-explanation-proof。简单的方法就是先排序，O(nlgn)。python可以直接用extended slicing来assign。值得注意的是哪个点开始：因为从0开始的偶数点（0，2，4，。。。)只可能和奇数点等长或者多1个，所以取median作为小于部分的最后一个元素是正合适的（无论奇偶）。O(n)的方法本质类似，就是用quick selection O(n)找到median，然后再一个一个按序插入。
错误点：

• 插入顺序：大的在odd index，小的在even index，而大的从左向右（start at 0）而小的从右向左（最后一个坐标在even位置）

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        kths = sorted(nums)
        m = kths[(n-1)/2]
        res = [0]*n
        j = 1
        k = n-1 if n & 1 else n-2
        # print m,j,k
        for i in xrange(n):
            #print m,j,k
            if nums[i]>m:
                res[j]=nums[i]
                j+=2
            elif nums[i]<m:
                res[k]=nums[i]
                k-=2
        #print m,j,k
        for i in xrange(n):
            if nums[i]==m:
                if k>=0:
                    res[k]=m
                    k-=2
                else:
                    res[j]=m
                    j+=2
        nums[::] = res[::]