求教一个面试题

有一个数组a，有一个数字k，这个数组满足：如果j-i>=k，则a[j] > a[i]。然后要把数组排序。请问有什么好的思路吗？
我的一个想法是，如果k比较小，可以获取若干个间隔是k的子数组然后用merge multiple sorted array的方法合并。但是感觉也不是太好

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的数组，而这点已知（用基于比较的排序法）是不可能的。

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 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组？

是哪种情况？

先build一个 map (A[i] -> i)  key is the value of the iTH element ,  and value is the index i.
然后sort  array A  base on map.get(A[j]) >= k + map.get(A[i])

抛块砖先

O(N Log K)的做法：

• PQ on the first K elements
• 滑动窗口加入下个
• 同时把PQ的最小写出。
  

14417335 发表于 2019-3-31 07:23
O(N Log K)的做法：

PQ on the first K elements

嗯嗯谢谢，这个是可行的。
但是我感觉没有完全利用已有信息，比如如果条件改成 if j == i + k, a[j] > a[k]，这个做法感觉也是可行的？

不过我也没想到啥更好的办法，谢谢啦

Scala688 发表于 2019-3-30 20:45
先build一个 map (A -> i)  key is the value of the iTH element ,  and value is the index i.
然后sor ...

没太看懂。。。能说的详细一点吗？这个map有什么用呢？

a[j]>a 是什么意思

gui59106375 发表于 2019-3-31 09:55
a[j]>a 是什么意思

？？我写的a[j] > a[i]，难道显示有问题？

yayafuture 发表于 2019-3-31 09:56
？？我写的a[j] > a，难道显示有问题？

啊还真有问题，是a.index(j) > a.index(i)

yayafuture 发表于 2019/03/31 22:57:23


啊还真有问题，是a.index(j) > a.index(i)

这样看来，数组本身属于整体有序，局部无序的情况，类似于
[[2,5,1],[38,12,24],[200,105,177]] 这样的数组。按照k长度切割数组，感觉merge不是很需要，每个sublist排序都是klgk， 一共n/k个， 最后整体是nlgk 复杂度，题目有什么要求吗？

gui59106375 发表于 2019/03/31 23:45:22


这样看来，数组本身属于整体有序，局部无序的情况，类似于
[[2,5,1],[38,12,24],[200,105,177]] 这样的数组。按照k长度切割数组，感觉merge不是很需要，每个subl...

谢谢 我也是看的面经 不太清楚最优复杂度是怎样