首页 文章

查找两个数组是否包含相同的整数集，没有额外的空间且比NlogN更快

提问于
浏览 次
26

我遇到了这个post，报告了以下的采访问题：

给定两个数字数组，找出两个数组中的每个数组是否具有相同的整数集？建议一个比NlogN跑得更快但没有额外空间的算法？

我能想到的最好的是以下几点：

  • （a）对每个数组进行排序，然后（b）有两个指针沿两个数组移动并检查是否找到不同的值...但步骤（a）已经有NlogN复杂性:(

  • （a）扫描最短的数组并将值放入 Map 中，然后（b）扫描第二个数组并检查是否找到了不在 Map 中的值...这里我们有线性复杂度，但我们使用额外的空间

......所以，我想不出这个问题的解决方案 .

想法？

谢谢你的所有答案 . 我觉得很多都是对的，但我决定选择ruslik's one，因为它提供了一个我没想到的有趣选项 .

arrays algorithm

14 回答

  • 0

    您可以通过选择用于累积的交换函数（例如，加法或XOR）和参数化散列函数来尝试概率方法 .

    unsigned addition(unsigned a, unsigned b);
unsigned hash(int n, int h_type);

unsigned hash_set(int* a, int num, int h_type){
    unsigned rez = 0;
    for (int i = 0; i < num; i++)
        rez = addition(rez, hash(a[i], h_type));
    return rez;
};

    以这种方式，在您确定误报概率低于某个阈值之前的尝试次数将不依赖于元素的数量，因此它将是线性的 .

    EDIT ：在一般情况下，集合相同的概率非常小，因此使用多个散列函数进行的O（n）检查可用于预过滤：如果它们确实不同或者是否存在概率，则尽可能快地确定它们是等价的，如果应该使用缓慢的确定性方法 . 最终的平均复杂度将是O（n），但最坏的情况将具有清除方法的复杂性 .

    回复于
  • 2

    你在问题中说“没有额外的空间”，但我认为你实际上是指“带有O（1）额外空间” .

    假设数组中的所有整数都小于k . 然后你可以使用in-place radix sort在时间O（n log k）中用O（log k）额外空间（对于堆栈，按照注释中的yi_H指出）对每个数组进行排序，并在时间O（n log）中比较排序的数组K） . 如果k不随n变化，那么你就完成了 .

    回复于
  • 0

    我假设所讨论的整数具有固定大小（例如32位） .

    然后，radix-quicksorting两个阵列就位（又名"binary quicksort"）是恒定空间和O（n） .

    在无界整数的情况下，我相信（但不能证明，即使它可能是可行的）你不能打破O（n k）障碍，其中k是任一阵列中最大整数的位数 .

    这是否优于O（n log n）取决于假设k如何与n一起缩放，因此取决于访调员对您的期望 .

    回复于
  • 0

    一个特殊的，而不是更难的情况是当一个数组包含1,2，...，n时 . 这被多次讨论过：

    尽管尝试了许多尝试，但没有显示使用O（1）空间和O（n）时间的确定性解决方案 . 您可以以某种方式欺骗要求（重用输入空间，假设整数有界）或使用概率测试 .

    可能这是一个悬而未决的问题 .

    回复于
  • -2

    这是一个co-rp算法：

    在线性时间内，迭代第一个数组（A），构建多项式Pa = A [0] - x）（A [1] -x）...（A [n-1] - x） . 对阵列B执行相同操作，命名此多项式Pb .

    我们现在想回答“是Pa = Pb？”的问题 . 我们可以概率地检查这个如下 . 从范围[0 ... 4n]中随机均匀地选择数r，并在线性时间内计算d = Pa（r）-Pb（r） . 如果d = 0，则返回true;否则返回false .

    为什么这个有效？首先，观察如果两个数组包含相同的元素，那么Pa = Pb，所以对于所有r，Pa（r）= Pb（r） . 考虑到这一点，我们可以很容易地看到这个算法永远不会错误地拒绝两个相同的数组 .

    现在我们必须考虑数组不相同的情况 . 通过Schwart-Zippel引理，P（Pa（r）-Pb（r）= 0 | Pa！= Pb）<（n / 4n） . 因此，当它们不相同时，我们接受两个数组的概率是<（1/4） .

    回复于
  • 1

    这类问题的通常假设是Theta（log n）位词，因为这是索引输入所需的最小值 .

    • sshannin的多项式 - 评估答案在有限域上工作正常，这避免了有限精度寄存器的困难 . 我们所需要的只是适当的素数（在支持的相同假设下很容易找到）（Z / 2）[x]中适当程度的很多公钥加密或不可约多项式（这里的难度很快就是多项式乘法，但我认为算法是o（n log n）） .

    • 如果我们可以修改输入，并且必须保持相同的设置，那么找到基数排序的空间并不是很难 . 从每个数组中选择第（n / log n）个元素并对两个数组进行分区 . 对大小 - （n / log n）块进行排序并进行比较 . 现在在size-（n-n / log n）块上使用基数排序 . 从先前处理的元素，我们可以获得n / log n位，其中如果a [2 * i]> a [2 * i 1]则位i打开，如果a [2 * i] <a [2 * i则关闭i 1] . 这足以支持具有n /（log n）^ 2桶的基数排序 .

    回复于
  • 3

    在代数决策树模型中，已知Omega（NlogN）下限用于计算集合交集（不考虑空间限制） .

    例如，请看这里：http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/06-algebraic-tree.pdf

    因此，除非你采用巧妙的位操作/散列类型方法，否则你不能比NlogN做得更好 .

    例如，如果仅使用比较，则不能比NlogN做得更好 .

    回复于
  • 11

    如果您对数字范围有一些限制，则可以打破O（n * log（n））障碍 . 但如果你不能使用任何额外的内存（你需要非常愚蠢的限制才能做到这一点），这是不可能的 .

    我还要注意，如果你有O（1）空间限制，即使O（nlog（n））排序也不容易，因为合并排序使用O（n）空间和quicksort（甚至不严格o（nlog（ n））需要堆栈的O（log（n））空间 . 你必须使用heapsort或smoothsort .

    有些公司喜欢提出无法解决的问题，我认为这是一个很好的做法，作为一名程序员，你必须知道什么是可能的，如何编码，还要知道有什么限制，所以你不要浪费你的时间一些不可行的事情 .

    请查看此问题以获得一些好的技巧：Algorithm to tell if two arrays have identical members

    回复于
  • 0

    对于每个整数 i ，通过迭代数组，检查两个数组中 i 的出现次数是零还是非零 .

    由于整数的数量是常量，因此总运行时间为 O(n) .

    不，我不会在实践中这样做 .

    回复于
  • -1

    只是考虑是否有一种方法可以散列两个数组的累积并进行比较，假设散列函数不会产生两种不同模式的冲突 .

    回复于
  • -1

    为什么我找不到一个数组的所有元素的和，产品，xor，并将它们与另一个数组的元素的相应值进行比较？

    如果它是这样的话，两个数组的元素的xor可以给出零

    2,2,3,3 1,1,2,2

    但是，如果你比较两个数组的元素的xor是相等的???

    考虑一下

    10,3 12,5

    这两个数组的xor都是一样的！ （10 ^ 3）=（12 ^ 5）= 9但他们的总和和产品是不同的 . 我认为两组不同的元素不能有相同的总和，产品和xor！这可以通过简单的比特值检查来分析 . 这种方法有什么不对吗？

    回复于
  • 6

    我不确定是否正确理解了这个问题，但是如果你对两个数组中的整数感兴趣：

    如果N >>>>> 2 ^ SizeOf（int）（整数（16,32,64）的位数）有一个解决方案：

    a = Array(N); //length(a) = N;
b = Array(M); //length(b) = M; 
//x86-64. Integer consist of 64 bits.

for i := 0 to 2^64 / 64 - 1 do  //very big, but CONST
  for k := 0 to M - 1 do
    if a[i] = b[l] then doSomething;   //detected

for i := 2^64 / 64 to N - 1 do
 if not isSetBit(a[i div 64], i mod 64) then
   setBit(a[i div 64], i mod 64);

for i := 0 to M - 1 do
 if isSetBit(a[b[i] div 64], b[i] mod 64) then doSomething; //detected

    O（N），没有附加结构

    回复于
  • 1

    我所知道的是，基于比较的排序不可能比O（NlogN）更快，因此我们可以消除大多数基于“常见”比较的排序 . 我正在考虑做一个桶排序 . 也许如果在面试中询问这个qn，最好的回答首先是澄清这些整数所代表的数据类型 . 例如，如果它们代表人的年龄，那么我们知道int的值的范围是有限的，并且可以在O（n）处使用桶排序 . 但是，这不会到位......

    回复于
  • 1

    如果数组具有相同的大小，并且保证不重复，则对每个数组求和 . 如果值的总和不同，则它们包含不同的整数 .

    编辑：然后您可以对数组中条目的日志求和 . 如果它也相同，那么数组中的条目相同 .

    回复于

相关问题