324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example: (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note: You may assume all input has valid answer.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

s思路: 1. 这道题一看，首先想到是用sort(),然后把后半部分和前半部分混和，例如:[1, 5, 1, 1, 6, 4],sort后得到[1,1,1,4,5,6],然后混合得到，[1,6,1,5,1,4].但这样的复杂度是o(nlgn) 2. 题目要求o(n), 仔细想，这道题之要求wiggle sort,只要有这个wave的效果，并不需要严格的排序。那就用quick select先找到中点，然后把和中点值相等的通过three way partition给gather到靠近中点的位置，最后得到的就左边值小的一个group,中间相等的一个group,右边值稍微大的一个group.三个group得到后，一样的进行混合，考虑到中间值可能重复的很多，在混合的时候，需要左右两个part都从最大的值来混合，保证wiggle sort的 nums[0] < nums[1] > nums[2] < nums[3]….性质，而不用担心出现相等的情况！ 3. 总结一下过程：首先，quick select,把中间值放在(n-1)/2的坐标位置上，并且左边是小于等于这个值，右边是大于等于这个值，代码中就是findMedian()这个函数，回忆一下这个函数的过程：初始时，left=0,right=n-1,k=(n-1)/2,然后选用left的位置作为pivot,然后找这个值在排好序的序列中的位置，这个找的过程可以写成一个独立的子函数叫partition,就是用two pointer来比较确定这个pivot应该放的位置，例如：让i=left+1,j=right,然后i和left比较，j和left比较，最后希望是o(n)找到left正确的位置即可，然后swap。这个过程就是quick sort的思想；第二步，由于第一步quick select只是把找到中值的位置，并且让小于等于中值的数在左侧，大于等于的在右侧，这就有一个问题了，等于中值的可能分布在任意位置，必须把等于中值的放在一堆，才能保证nums[0] < nums[1] > nums[2] < nums[3]….，否则可能出现相等的情况，因此用threewaypartition用三个指针把数分堆，让等于中值的数集合在一起。这里回忆一下整个过程，写得很妙。 4. 接上文。因为要分三堆，也算是排序了，不过是很粗略的排序，用两个指针分别指向左右边界，然后用一个指针来遍历所有的数，一共就三个指针，这是在做之前就要明确的问题的本质和解题的规模。一共有两种设置指针的方式，如下图：图的上半部分是把left和right指针的初始位置分别放在序列的两端，这样做，left往右移动，right往左移动，最后是融合成一部分；图下半部分是另一种，把left和right初始位置放在了中值位置的左右，这么做，left则往左移动，right则往右移动，最后是分开的。所以在编写代码的时候，也发现第一种代码简单，但理解起来略困难，第二种则代码复杂一些，但理解起来很容易，提供两种思路，还是想说明：没有那一种就一定比另一种好，只是站在不同的位置看待同一个问题。 5. 继续描述。在找中值的时候，还可以利用c++的库函数nth_element(start iterator, mid iterator, end iterator)比自己写的都快！ 6. 这道题，最后要求做到o(1)的空间复杂度，就不容易了，因为上面的方法还是需要o(n)的空间。参考https://discuss.leetcode.com/topic/32929/o-n-o-1-after-median-virtual-indexing　膜拜牛人一下，看得似懂非懂了！以后再思考！