求教一个面试题

stellari 发表于 2019-4-1 05:36
k=5,[1,2,3,5,4,4,3,4,6,6]这个例子也是我举的……

所以你需要再明确一下“组”的定义。你之前说“一 ...

额。我说错了,对不起。。。。我的意思是分为k个组。按这个例子来说就是分为：
14
23
34
56
46
串接起来就是
1,4,2,3,3,4,4,6,5,6

补充内容 (2019-4-1 08:06):
但是这种思路应该是不正确的。。。

raistlins 发表于 2019-4-1 03:58
我也只想得到PQ merge sort 那个方法。但是我有个不成熟的想法，需要有数学好的来证明下行不行，或者举个反 ...

说错了，是分为k个组。
我仔细想了一下，觉得并不能证明这种方法是正确的。
但是一时之间又想不出反例来。。。

补充内容 (2019-4-1 08:05):
额。这种解法确实不对。实在想不出O(n)的解法了.....