求教一个面试题

yayafuture 发表于 2019-4-1 01:22
谢谢 我也是看的面经 不太清楚最优复杂度是怎样

这题是面经里的？哪个公司，出现次数多不多？多的话请告知我把它归入高频题。

gui59106375 发表于 2019-3-31 23:45
这样看来，数组本身属于整体有序，局部无序的情况，类似于
[[2,5,1],[38,12,24],[200,105,177]] 这样的数 ...

这样做的话，恐怕还是需要merge的，因为第n段和第n+1段间总会存在距离差<k的pair，所以并不能保证n+1段的任意元素>第n段中任意元素

比如
k = 5
[1, 2, 3, 5, 4 | 4, 3, 4, 6, 6]

14417335 发表于 2019-3-31 12:45
这题是面经里的？哪个公司，出现次数多不多？多的话请告知我把它归入高频题。

是pony.ai的一个面经里提到的，频率应该不高吧我只在地里见过一次，网上也没搜到相关的

我也只想得到PQ merge sort 那个方法。但是我有个不成熟的想法，需要有数学好的来证明下行不行，或者举个反例

一共可以分为n/k个组，按每组的第一个元素大小，把这n/k个组串接起来。
然后从头到尾跑一遍冒泡

总共是O(n)



补充内容 (2019-4-1 05:40):
说错了，是分为k个组。
我仔细想了一下，觉得并不能证明这种方法是正确的。
但是一时之间又想不出反例来。。。

yayafuture 发表于 2019-3-31 21:57
嗯嗯谢谢，这个是可行的。
但是我感觉没有完全利用已有信息，比如如果条件改成 if j == i + k, a[j] > a ...

题目这样改的话，这个算法就失效了。因为该算法可行的前提条件是：

任意时刻，当前剩余序列a'的最小值一定在PQ中


而这个条件等价于：

1. 整个序列a的最小值一开始在PQ中，
2. 如果剩余序列a'的最小值在PQ中，那么a'的次最小值要么已经在PQ中（即剩余序列a'的前k个元素），要么是即将被加入PQ的元素（即第k+1个元素）

其中条件2非常重要，因为它保证了执行完“2. 滑动窗口加入下个"后，最小值和次最小值都在PQ中。这样在“3. 同时把PQ的最小写出”后，下一个最小值一定在PQ中。但如果原题改为j == i + k，上述条件2就不能满足，比如这个例子：

k = 5
[6 5 3 4 2 | 7 6 4 5 3]

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

能否详细解释一下“按每组的第一个元素大小，把这n/k个组串接起来”？如果k个元素为一组的话，第i-1组的首元素一定<第i组的首元素，也就是说这些组已经是按首元素大小排好序的了。或者你说的“串接起来”是另外的意思？

另外，如果是用基于比较法的排序，那这道题时间复杂度不可能低于O(Nlogk). 因为假设存在复杂度为O(f(N, k)) < O(Nlogk)的神秘算法A，那么我只要将N/k个长为k的乱序小数组首尾连成一个长为N的大数组，然后对每个数组的元素进行scaling（比如第一个数组的元素scale到[0,1)范围，第二个数组scale到[1,2)范围…），保证大数组的性质符合题意。然后调用A算法，对整个大数组排序，排序之后，我再从左往右扫描一遍排序后的大数组，根据每个数的值，我可以在O(1)时间内判断出它是来自哪个小数组，然后将这个数放回到原来的小数组中。

这样做的净效果是将原来的N/k个乱序小数组各自排了序。因为scaling和最后的放回都需要O(N)时间，因此最后的总时间复杂度是O(N+f(N,k) + N) = O(max(N, f(N, k))。而f(N, k) < Nlogk，也就是说我们平均能在<O(klogk)时间里排序每个长为k的数组，而这点已知（用基于比较的排序法）是不可能的。

stellari 发表于 2019-4-1 04:34
能否详细解释一下“按每组的第一个元素大小，把这n/k个组串接起来”？如果k个元素为一组的话，第i-1组的 ...

i-1组的首元素不一定小于i组首元素。上面有同学举过例子了。比如k=5,[1,2,3,5,4,4,3,4,6,6]。也就是说在0~k-1之间的元素，不能确认谁大谁小，而这k个元素就是我说的各组的首元素。同时，你也可以发现，第1个元素和第k个元素，其实也不能确认大小关系的。

补充内容 (2019-4-1 05:03):
比如k=2, [1,5,2,6,9,7]

stellari 发表于 2019-4-1 04:34
能否详细解释一下“按每组的第一个元素大小，把这n/k个组串接起来”？如果k个元素为一组的话，第i-1组的 ...

串接起来的意思是说类似于radix sort的第一步。

stellari 发表于 2019-4-1 04:01
题目这样改的话，这个算法就失效了。因为该算法可行的前提条件是：

任意时刻，当前剩余序列a'的最小值 ...

前面说的很有道理，但是这个反例不成立啊。所谓的滑动窗口加入下一个值，不是直接加入idx+1，而是第idx+k个元素。以你举的例子来说， 前k个元素最小值是2，idx是4,pop出来之后，加入的是3,idx是9.

raistlins 发表于 2019-4-1 05:01
i-1组的首元素不一定小于i组首元素。上面有同学举过例子了。比如k=5,[1,2,3,5,4,4,3,4,6,6]。也就是说在0 ...

k=5,[1,2,3,5,4,4,3,4,6,6]这个例子也是我举的……

所以你需要再明确一下“组”的定义。你之前说“一共可以分为n/k个组”，所以我以为你的意思是分成[1 2 3 5 4]和[4 3 4 6 6]这n/k = 2组。

但是你这楼又说“k个元素是各组的首元素”，那也就是说总共应该是k组？

是哪种情况？