-3

我有以下问题：

给定两个大小为 m 和 n 的不同整数 A 和 B 的数组，找到第一个公共元素的上限复杂度是多少？除了输入数组之外，我最多可以使用 O(k) 内存。

k 是一个常数（意味着除了输入之外我只能使用常数内存）

我已经在另一个网站上问过这个问题：

https://cs.stackexchange.com/questions/12182/lower-bound-complexities-for-finding-common-elements-between-two-unsorted-arrays

但没有解决问题

4

1 回答 1

0

我将对您在 CS 上的原始帖子中的第二个问题进行破解，因为我不确定您对问题的总结是否是最好的。

给定两个大小为m和n的不同整数A和B的未排序数组；知道数组之间的公共元素在两个数组中具有相同的相对顺序，并且对于每两个连续的公共元素，它们的距离最多为k（常数），确定两个数组之间的所有公共元素保持它们的相对顺序并使用除了输入数组之外，最多O(k)内存。

我将再次使用评论和您对原始问题的编辑中提到的堆，但这次我们只需要一个堆。

请注意，为了确定元素A [i] 是否在数组B中匹配，我们只需要检查元素B [ik].. B [i+k]。在B的子数组上使用 heapify在O(k)时间和 2k+1 = O(k)空间中构造这些元素的堆B'。确定B'中是否存在与A [i]的匹配项需要O(log k)。然后我们遍历A for i=1..m，更新B'并检查与A的匹配[一世]。这保持了输出中的相对顺序。要确定A中的所有m个元素是否匹配需要O(km log k)或O(m)时间。

笔记：

  • 显然，您应该遍历较小的数组，将较大数组的元素放入堆中。我一直假设m <= n。
  • 您永远不必一次将超过 k+1 个元素放入堆中，这将在检查 A 的第一个元素时发生。在检查某些元素A [i ], k < i < mk。在这个范围之外，堆总是更小。
  • 一旦 i 在 k < i < mk 范围内，如果当前索引上没有匹配项，您只需添加一个元素并从堆中删除一个元素即可检查下一个索引。
  • 如果有一个匹配，比如在A [i] 和B [j]，你仍然必须添加最多一个元素，但是你可以从堆中删除所有索引小于或等于 j 的元素（因为我们知道元素具有相同的相对顺序，因此A [i+1] 不会匹配B [j+1] 之前的任何内容）。在某些时候，简单地用元素B [j+1].. B [i+k] 重建堆可能会变得更有效。
  • 一旦我们的堆增长到其最大大小 2k+1，我们总是删除至少与我们添加的元素一样多的元素。因此我们的堆永远不会大于 2k+1。
于 2013-06-11T17:26:10.247 回答