查找有限制的两个数组之间的交集
为了在两个数组之间找到相同的数字，我必须编写一个程序。问题是，我必须以最优化的方式，尊重一些约束：
数组A和w的-Having i，j索引，数组B的x索引，如果Ai=Bw、Aj=bx和I
这些数字之间的-The最大距离必须是k(由输入给出)；
为了实现优化搜索，-I必须在最大O(k)空间使用；
-The数字在每个数组中只出现一次(比如集合)。
为了优化搜索过程，我考虑用第一个数组的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:在输出中，数字必须以与数组中相同的顺序出现。
回答 1
Stack Overflow用户
发布于 2013-11-14 03:27:46
用K作为最大距离
假设当您说它们必须按数组顺序显示时，来自一个数组的顺序就足够了--假设：
A: 1 2 B: 2 1
结果为1 2或2 1，而不是1或2，因为顺序是交叉的。
请注意，K约束使这个问题不太理想。
第一个观察是，大数组中的任何内容，超过较小数组+k-1中元素数量的索引，都可以忽略。
第二个观察是，所有的值显然都是int。
第三个观察是，对于具有接近数组大小的K的大型数组，这必须是最优的。
基数排序是O(N)，取O(N)大小，所以我们将使用它
为了允许K，我们可以将两个数组复制到并行数组(值、位置)，而不是复制在大数组中不可达的值，如观察1( A: 71，23，42 ==> A2：{ 71，0 }，{ 23，1 }，{ 42，2})
我们还可以为结果创建一个与较小数组大小相同的类似数组。
我们可以修改基排序以将值和位置移动到一起。
Algorythm：
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) ]https://stackoverflow.com/questions/18152011
复制相似问题
腾讯云开发者
