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].

Follow Up:

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

解题方法

因为这一题不能等于，如果采取和I一样的方法，遇到重复的元素没办法处理，所以遍历比较 相邻两个的办法不可行。

先排序

依然，没有想法就先排序。排序后思路就比较明确了。

  1. 将sorted数组分为前后两个部分
  2. 奇数位，从前半部分的末尾开始取
  3. 偶数位，从后半部分的末尾开始取

注意： 必须要倒着取，因为中间有可能有重复元素，如果是正着取的话，重复元素会 靠在一起。 比如[1,2,5,5,5,6]从前面取就会变成 [1,5,2,5,5,6]。因为肯定有满足条件的排序，所以重复元素 不能超过数组长度的1/2. 所以当从后往前取的时候，不会遇到重复元素相邻的情况

O(n)的做法

先找到中位数median，中位数可以通过find-kth-element的quickselect方法找到，avg是O(n)

然后我们找到了中位数，通过这个特性我们可以将数组元素分为3组：

  • median, 高

  • == median, 中
  • < median, 低

然后在最终的结果中，将顺序变为 高-中-高-中-高-中。。。。-中-高-低-中 就可以了

而这个过程中，我们可以使用类似sort colors的方法，因为在quickselect的过程中，原来的array已经 变成了 高高高中中中低低低

Let's say nums is [10,11,...,19]. Then after nth_element and ordinary partitioning, we might have this (15 is my median):

index:     0  1  2  3   4   5  6  7  8  9
number:   18 17 19 16  15  11 14 10 13 12

转变后的就应该变成, 奇数位是18, 17, 19, 16, 15，偶数位是11, 14, 10, 13, 12

index:     5  0  6  1  7  2  8  3  9  4
number:   11 18 14 17 10 19 13 16 12 15

要得到这个排序，我们定义一个函数

def new_index(idx, n):
    return (2*idx + 1) % (n | 1)

n | 1得到最近的不小于n的奇数。

解释：

  • 前半部分原index 0,1,2,3,4 对应的是 1, 3, 5, 6, 9，我们可以看到这个关系是 2 * i + 1
  • 后边部分原index 5,6,7,8,9 对应的是 0, 2, 4, 6, 8, 要用同样的公式 2 * i + 1, 就应该 % 11

如果本来长度就是奇数11，那么

  • 后半部分5,6,7,8,9,10 对应 0,2,4,6,8,10 -> 还是 % 11

总结： 因为mid point要对应到0, 所以应该是2 * mid + 1， 将长度取到最近的不小于它的奇数

Solution

先排序

这里必须借助一个o(n)的space, 因为要根据sorted后的结果来判断，而不能改变这个sorted array

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        sorted_nums = sorted(nums)

        for i in range(1, length, 2):
            nums[i] = sorted_nums.pop()

        for i in range(0, length, 2):
            nums[i] = sorted_nums.pop()

O(n)解法

Reference