1

我必须编写一个程序才能在两个数组之间找到相同的数字。问题是我必须以最优化的方式来尊重一些约束：

- 如果 A[i]=B[w] 和 A[j]=b[x] 并且 i 具有数组 A 的 i,j 索引和数组 B 的 w,x 索引

- 这些数字之间的最大距离必须为 k（由输入给出）；

-我必须使用最大 O(k) 空间来实现一些优化搜索的东西；

- 数字在每个数组中仅出现一次（如集合）。

我正在考虑用第一个数组的 k 个元素构建一个平衡的 RBTree 以优化搜索过程，但我怀疑它需要的空间（我认为它不是 O(k)，因为指针和颜色标记）。

有人对这个问题有更好的了解吗？

编辑：我将把我的例子放在这里更清楚：

  • 阵列 A：3 7 5 9 10 15 16 1 6 2
  • 阵列 B：4 8 5 13 1 17 2 11
  • 常数 k = 6
  • 输出：5 1 2

Edit2：在输出中，数字必须以与它们在数组中相同的顺序出现。

4

1 回答 1

0

使用 K 作为最大距离

假设当您说它们必须以数组顺序呈现时，来自一个数组的顺序就足够了 - 假设：

答：1 2 B：2 1

导致 1 2 或 2 1 而不是 1 或 2，因为顺序是交叉的

请注意，K 约束使其不太理想

第一个观察是较大数组中的任何内容，超过较小数组中元素数量的索引 + K -1 可以忽略

第二个观察结果是所有值显然都是int

第三个观察结果是，对于具有接近数组大小的 K 的大型数组，这必须是最佳的

基数排序是 O(N) 并且需要 O(N) 大小，所以我们将使用它

为了允许 K 我们可以将两个数组复制到 (value, position) 的并行数组，而不是根据观察 1 复制较大数组中无法访问的值，即 A: 71, 23, 42 ==> A2: { 71 , 0 }, { 23, 1 }, { 42, 2 }

我们还可以为与较小数组大小相同的结果创建一个类似的数组

我们可以修改基数排序以将值和位置一起移动

算法：

1) Copy arrays [ O(1) ]

2) Radix sort array A and B by values [ O(1) ]

3) Walk A and B: [ O(1) ]
if A < B -> increment index in A
if A > B -> increment index in B
if A == B -> incremnt index in A and B
             add original A to result IF the pos diffence is less than K    
4) Radix sort results by position [ O(1) ]

5) print result values [ O(1) ]
于 2013-11-14T03:27:46.597 回答