No.0018-CareerCup

题目描述

Given an array of length N and an integer K, sort the array as much as possible such that no element travels more than K positions to its left -- however it can travel as much as it likes to the right.
给一个长度为N的数组和整数K，要求尽可能排序，前提是元素不能左移超过K，但是对右移没有限制。

信息补全

这个题目算比较模糊的那种，需要问一些问题。
数组的元素都是数字吗？假设是。
数组里面有相同的元素吗？假设可能有。
所谓排序，要求升序还是降序？假设是升序。
什么叫做“尽可能”？假设按要求排完序之后，出现一对反序对，那么排序效果就弱一分。这样反序对的数量可以作为一个量化指标。比如升序前提下12354就比12534的排序效果好，因为前者只有(5,4)一对反序，而后者有(5,3)(5,4)两对。当然这个是我脑补的。

思路解析

暴力破解

这个题不是特别好暴力破解，但如果了解了对排序效果的评价指标，也可以尝试分析。
本身一个长度为N的数组有N!种排列。
评价一个序列，很明显要O(n^2)的时间复杂度。
然后还需要判断是不是左移超过了限制。好像除了一个个来找也没啥更好的办法，这样还是O(n^2)。
这样下来时间复杂度突破天际。

更好的办法

其实，主要的限制就是在于左移不超过K。
回忆主流的各种排序方法，有什么方法能比较好地实现这个目标？
归并排序，快速排序，堆排序。
归并的话，没有什么直观的限制手段。
快速也是，交换的时候没办法妥协。
唯有堆排序。我搞一个长度为K+1的堆来排序不就行了吗？
具体描述如下：先把数组的前K+1个元素入堆，当然是最小堆，然后每次pop最小值出来，然后假如数组还有元素，就再加入一个新的元素。
这样就能保证限制条件的满足。假设原数组是A，排序之后是B，考虑极限情况，第一批元素，就算A[K]第一个pop出来为B[0]，左移距离也就是K。而之后的元素进来时，B前面的坑已经被占了，所以极限情况还是K。
时间复杂度O(nlogk)，空间复杂度O(k)。
至于这样算不算“尽可能”？我直觉是认为这个就是限制下的最好情况了。
假设还有一个A的排序C，在满足限制的条件下比B排序效果更好，也就是说B比C至少要多一对反序对，但是B和C可能顺序完全不一样……算了，这证明我不会。

代码

from heapq import heapify, heappush, heappop
class Solution(object):
    def sol(self, n, k):
        h = n[:k+1]
        heapify(h)
        i = k+1
        ret = []
        while i < len(n):
            ret.append(heappop(h))
            heappush(h, n[i])
            i += 1
        while h:
            ret.append(heappop(h))
        return ret

总结

这个题属于比较巧的那种，测试的是一种思维。会者不难，难者不会。