Google on-site最后一面非常难的一道题目

LZ
这一题我也被考过，其实关键就在于找到一个中位数。
这题转化一下就变成了Kth largest/smallest 了。如果你能找到中位数，那么排在中位数左边和右边的数交叉放置到新的list里面就ok了，是可以O(n)的。
最简单的方法就是先排序，然后最左+最右+最左+最右这样循环下去就可以排列了，但是要排序的花算法要到O（nlogn）。
而且排序其实和第一种想法思路一样，只不过条件更严苛所以时间复杂度大了

这个是wiggle sort 是google很喜欢问的一道题 我电面也被问过了。。

听你们说了这么做，我在纸上画了画，逐步移动就给出解了，ON复杂度。。。0空间

Python version:

#!/usr/bin/env python
import random

class Solution:
    def genSawArray(self, input):
        if len(input) < 3:
            return input
        output = list(input)
        for index, value in enumerate(output):
            if not index % 2:
                continue
            # odd index is not in the end
            if index != len(output) - 1:
                tmp_arr = [output[index - 1], output[index], output[index + 1]]
                output[index] = max(tmp_arr)
                output[index - 1] = min(tmp_arr)
                output[index + 1] = sum(tmp_arr) - output[index - 1] - output[index + 1]
            # odd index is in the end
            else:
                output[index - 1] = min(output[index - 1], output[index])
                output[index] = max(output[index - 1], output[index])
        print output


if __name__ == "__main__":
    arr = random.sample(range(30), random.randint(7, 15))
    print arr
    solution = Solution()
    solution.genSawArray(arr)

Test:
enzo@enzo-ubuntu:~/Documents/code/todel$ python wigglesort.py
[26, 24, 7, 22, 14, 8, 2, 11]
[7, 26, 14, 43, 2, 51, 11, 11]
enzo@enzo-ubuntu:~/Documents/code/todel$ python wigglesort.py
[13, 11, 8, 1, 3, 16, 18, 19, 23, 27, 22, 24, 12, 26, 0]
[8, 13, 1, 16, 16, 18, 16, 23, 19, 27, 12, 27, 0, 39, 65]
enzo@enzo-ubuntu:~/Documents/code/todel$ python wigglesort.py
[2, 13, 26, 12, 29, 19, 5, 23, 18]
[2, 26, 12, 29, 5, 19, 18, 27, 32]

shuffle 这里是否要求随机等概率

Larrylianj 发表于 2015-3-22 01:44
Proof by induction:

(1) when there is only 1 number, it satisfies.

真心和你想的，写的，一模一样，完全没有get到这个题难在哪里。。。。