九章算法 | Snapchat 面试题 : K Spaced Array Sorting
撰文 | JZ
专栏 | 九章算法
题目描述
一个数组每隔k个数字是从小到大有序的，即arr[i] <= arr[i + k] <= arr[i + 2 * k] <= ....，请将这个数组从小到大排序。我们期望你能写出 O(n * logk) 复杂度的算法。
思路点拨
这题类似合并两个排序后的数组，用一个优先队列维护k个值即可做到题目要求的复杂度。
考点分析
本题考察了优先队列的运用，以及做题者的思维能力，想到了优先队列去维护k个间隔的大小关系，该问题即可迎刃而解。
九章参考程序
http://www. jiuzhang.com/solution/k -spaced-array-sorting/