4

这是一个编码面试问题。我们得到一个数组say ，我们只random_arr需要使用swap函数对其进行排序。

此外，每个元素的交换次数random_arr也是有限的。为此，您将获得一个数组parent_arr，其中包含 的每个元素的交换次数random_arr。

约束：

  1. 您应该使用交换功能。
  2. 每个元素可以重复最少 5 次，最多 26 次。
  3. 您不能将给定数组的元素设为 0。
  4. 您不应该编写辅助函数。

现在我将解释如何parent_arr声明。如果parent_arr是这样的：

parent_arr[] = {a,b,c,d,...,z} 然后

a can be swapped at most one time.

b can be swapped at most two times.

如果 parent_arr[] = {c,b,a,....,z} 那么

c can be swapped at most one time.

b can be swapped at most two times.

a can be swapped at most three times

我的解决方案：

对于 random_arr[] 中的每个元素，如果它已排序，则存储它下面有多少元素。现在从 parent_arr[] 中选择具有最小交换计数的元素并检查它是否存在于 random_arr[] 中。如果是并且它已经发生了不止一次，那么它将有多个可以放置的位置。现在选择具有最大交换计数的位置（而不是该位置的元素，非常宝贵）并交换它。现在减少该元素的交换计数并对 parent_arr[] 进行排序并重复该过程。

但它的效率很低，其正确性无法得到证明。有任何想法吗？

4

1 回答 1

4

首先，让我们简化您的算法；那么让我们非正式地证明它的正确性。

修改算法

请注意，一旦您计算了排序序列中每个数字下方的元素数，您就有足够的信息来确定每组相等元素x在排序数组中的位置。例如，如果c重复 7 次并且前面有 21 个元素，则cs 将占据范围[21..27]（所有索引都是从零开始的；范围包括其末端）。

按照掉parent_arr期数量增加的顺序进行。对于每个元素x，找到其目标范围的开始rb；还要注意其目标范围的结束re。random_arr 现在遍历范围之外的元素[rb..re]。如果您看到x，请将其交换到范围内。交换后，递增rb。如果你看到random_arr[rb]等于x，继续递增：这些xs 已经在正确的位置，你不需要交换它们。

正确性的非正式证明

现在让我们证明上述的正确性。请注意，一旦一个元素被交换到它的位置，它就再也不会移动了。当您到达 中的一个元素x时parent_arr，所有交换次数较少的元素都已被处理。通过构建算法，这意味着这些元素已经到位。假设x有k允许的交换数量。当您将它交换到它的位置时，您将另一个元素移出。

这个被替换的元素不可能，因为在目标范围内寻找目的地时x算法会跳过s 。此外，被替换的元素不能是 中下面的元素之一，因为下面的所有元素都已经在它们的位置，因此不能移动。这意味着被替换元素的交换计数必然或更多。因为当我们完成处理时，我们已经用尽了任何元素上的最多交换（这很容易通过归纳证明），我们交换出来以腾出空间的任何元素将至少有一个剩余的交换可以让我们交换当我们按照.x[rb..re] xparent_arrxk+1xkxparent_arr

于 2013-02-06T19:08:22.793 回答