找出对给定数组进行排序所需的"交换"数

Question

这是一个面试问题.A swap表示从数组中删除任何元素并将其附加到同一数组的后面.给定一个整数数组,找到swaps排序数组所需的最小数量.你能做得比O(n^2)吗？

例如:输入数组:[3124].数量swaps:2([3124] - > [1243] - > [1234]).

Answer 1

问题归结为找到排序数组的最长前缀,该前缀在输入数组中显示为子序列.这就决定了你的元素并不需要进行排序.其余的元素需要逐个删除,从最小到最大,并附加在后面.

在您的示例中,[3, 1, 2, 4]已经排序的子序列是[1, 2].最佳的解决方法是删除其剩余的两个元素,3并且4,在后面添加他们.因此,最佳解决方案是两次"交换".

可以O(n logn)使用O(n)额外的内存及时完成子序列的查找.以下伪代码将执行此操作(代码也恰好是有效的Python):

l = [1, 2, 4, 3, 99, 98, 7]
s = sorted(l)
si = 0
for item in l:
  if item == s[si]:
    si += 1
print len(l) - si

如果,在你的榜样,数组包含整数从置换1到n,问题就可以解决在O(n)一次使用O(1)记忆:

l = [1, 2, 3, 5, 4, 6]
s = 1
for item in l:
  if item == s:
    s += 1
print len(l) - s + 1

更一般地,只要我们先验地知道输出数组,就可以使用第二种方法,因此不需要通过排序找到它.

Answer 2

O(nlogn)即使我们不假设连续值数组,这也可能有效.
如果我们这样做 - 它可以完成O(n).一种方法是O(n)空间和O(nlogn)时间.
给定数组将Ait(O(nlogn))排序为第二个数组B.
现在...(数组从1索引)

swaps = 0
b = 1
for a = 1 to len(A)
  if A[a] == B[b]
    b = b + 1
  else
    swaps = swaps + 1