尽可能排序:值不能超过左侧的k个位置

Question

给定长度为N且整数为K的数组,尽可能地对数组进行排序,使得没有元素向左移动超过K个位置.然而,一个元素可以在它的右边行进.

让我们将排序定义为无序对的数量,即:排序度(1,2,3)= 0和排序度(3,1,2)= 2.

澄清:如果k+1数组的第一项移动到数组的末尾,则应将其他项视为向左移动k + 1个位置.

这是一个面试问题.我想过使用冒泡排序.外循环将运行K次,运行时间为O(nk).最小的整数将是向左移动K次的唯一整数.其他整数将向左移动少于K次.

有没有更有效的方法来解决这个问题？

Answer 1

使用最小堆对O(n log k)中的n个元素列表进行排序.

1. 将第一个k + 1个未排序的元素添加到堆中.
2. 重复此步骤:从堆中弹出min元素.将其添加到排序列表的末尾.将下一个未排序的元素添加到堆中.

因为堆总是最多有k + 1个元素而不管n,所有堆操作都是O(log k),总运行时间是O(n log k)

为什么这是正确的？

假设不是.然后对于某些输入,我的算法给出非最佳排序.让我成为这样一个输入,让A成为我算法的输出,让B成为最佳排序.

让我成为A和B不同意的第一个指数.令x = A [i],y = B [i],并且令j为B中的x的索引.

我声称在B中交换x和y可以改善B的排序,这是一个矛盾.

因为A和B对于i之前的位置是相同的,所以同一组k + 1个元素有资格进入两个位置i.因为我的算法选择x作为这些元素的min,我们知道x小于y.我们也知道j大于i.

当我们在B中交换x和y时会发生什么？

首先,请注意,排序的变化不受i左侧或j右侧的任何内容的影响,因为它们相对于x和y的位置不会被交换所改变.

我们知道i和j之间没有小于x的元素,因为我的sort选择了最小的可用元素.因此,i和j之间的所有元素至少与x一样大.

对于i和j之间的每个元素等于x,交换x和y可以将排序性提高1,因为我们相对于这些元素改进y并且x不受影响.

对于i和j之间的每个元素大于x,x相对于这些元素的排序性提高了1,而在最坏的情况下,相对于这些元素的y的排序性降低了1,因此净效应最差为0.

此外,交换x和y可将x相对于y的排序性提高1,因此此交换严格提高了整体排序.

矛盾.

Answer 2

天真的方法：

从左到右迭代数组。
对于每个位置，i我们考虑 中的一个子数组i to i+k。然后我们必须获取该子数组中的最小值元素，并将该子数组的第一个元素与该元素交换。
现在，转到位置i+1并做同样的事情。

优化方法：

我们可以使用线段树来解决这个问题。使用此数据结构，您可以找到数组任意范围之间的最小值，还可以在线编辑O(logn). 在您的问题中，我们可以使用以下步骤获取解决方案数组，

arr[1]= 位置 1 到 min(k,n) 之间的最小值，然后用无穷大编辑该位置
arr[2]= 位置 1 到 min(k+1,n) 之间的最小值，然后用无穷大编辑该位置
arr[3]= 位置 1 到 min 之间的最小值(k+2,n)，然后以无穷大编辑该位置
arr[4]= 位置 1 到 min(k+3,n) 之间的最小值，然后以无穷大编辑该位置
...
...
arr[n]= 位置 1 到 min 之间的最小值(k+n,n)，然后用无穷大编辑这个位置

整体复杂性O(nlogn)

例如：

given array = 5 3 4 7 8 2 1 0 and K = 2

使用此算法，您将得到如下解决方案数组：

3 4 5 2 1 0 7 8
sortedness value = 12

希望能帮助到你！

最好的问候，
阿加萨