测试非排序集合是否不相交的线性时间算法，（作业问题）

Question

问题: 两个集合A和B，每个集合都有n个元素。假设每个元素都是范围在[0, n^100]内的整数。这些集合不一定是排序的。请展示如何在O(n)的时间内检查这两个集合是否是不相交的。你的算法应该使用O(n)的空间。

我的原始想法是创建一个A集合的哈希表，并在其中搜索B集合中的每个元素。然而，我不知道有什么方法可以创建一个数据集的哈希表，它的范围只需要O(n)的空间。我应该考虑完全不同的方法吗？

更新： 我联系了教授关于这个问题，询问如何实现哈希表，他的回答是： 请注意，哈希操作仅在平均情况下需要O(1)时间。我们需要一个最坏情况下的O(n)时间算法来解决这个问题。

因此，看起来这个问题正在寻找一种不同的方法...

- ejf071189

---

确切地说应该是[0，n ^ 100]，而不是[0，2 ^ 100]吗？问题在于数n ^ 100具有100 * log n位数字。你甚至不能在O（n）时间内阅读其中的n个数字，更不用说对它们做任何事情了。也许问题在于这个问题自己混淆了n在这个问题中的含义，以及在复杂性分析中通常表示什么（输入的位数）。 - Steve Jessop

我重新检查了任务，范围肯定是[0，n ^ 100]。我想这个问题假设一个数字可以独立于其大小/位数被读取。 - ejf071189

嗯，如果问题假设如此，那么也许它会允许您存储指向数字的指针（O(1)空间独立于其位数），并且在独立于数字位数的情况下计算哈希码和比较值的时间为O(1)。荒谬的假设，但我认为否则这个问题是不可能的。 - Steve Jessop

根据数字的表示方式，有效的哈希方案可以利用数字的长度、一些最高有效位、最低有效位等，这将是O(1)的。 - Axn

@Steve，是的，你说得对。除非我们特别讨论位(bit)，否则O(lg n)位通常被认为是O(1)内存。 OP问题与范围为[0，n]相同，具有相同的标准哈希解决方案，只是额外增加了100的常数因子。 - jonderry

Answer 1

输入：数组A[m]，B[n]

输出：如果它们不相交，则为True，否则为False

---

1. 暴力方法：时间复杂度O(m*n)，空间复杂度O(1)

1. Search for each element of A into B
2. As soon as you get a match break and return false
3. If you reach till end, return true

优点：不修改输入内容

---

2. 同时排序 O(mlogm + nlogn + m + n)

1. Sort both arrays
2. Scan linearly

缺点：修改了输入内容。

---

3. 小数组排序 O((m + n)logm)

1. Say, m < n, sort A
2. Binary search for each element of B into A

缺点：会修改输入

---

4. 较大的排序 O((m + n)logn)

1. Say n > m, sort B
2. Binary search for each element of A into B

缺点：修改了输入内容

---

5.哈希 O(m + n)时间复杂度，O(m) 或 O(n)空间复杂度

优点：不会修改输入内容

- Rajendra Uppal

---

这个答案忽略了输入值的范围。当你限制输入值时，排序可能比Omega(n log n)更好（请参见我的答案）。 - Paul Hankin

Answer 2

为什么不使用哈希表呢？如果它们都是唯一的，创建哈希表的时间复杂度为O(n)，搜索的时间复杂度也为O(n)，总时间复杂度为O(2n) = O(n)，这不是很高效吗？

- Nicholas

---

担心的是空间问题。由于可能值的范围非常大，哈希表的空间是否会比O（n）更大？ - ejf071189

哈希表使用哈希函数将输入域缩小到适当的大小。 - Gareth Rees

我在实现哈希函数方面没有太多经验。我不确定是否可以仅说明使用了适当的哈希函数，使得哈希表的大小为O(n)，或者我是否实际上需要概述哈希函数的工作原理来解决这个问题。 - ejf071189

“哈希表是常数时间和线性空间”的假设非常普遍，尽管它并不严格正确。” - Craig Gidney

@Strilanc：同意，特别是因为有很多实现策略。但是，如果正确定义了域，应该可以选择这样的实现。 - Matthieu M.

Answer 3

哈希集合将适用。即使这并不严格正确，但认为哈希集/表每个操作是常数时间的做法非常普遍。

请注意，哈希集合/表绝对只使用与插入元素成比例的空间，而不是潜在的总元素数。您似乎误解了这一点。

如果“通常被认为足够好”在某些原因下不可接受，则可以使用基数排序。它是输入元素的总表示大小的线性时间。(注意：这与元素数量的线性时间略有不同。)

- Craig Gidney

---

实现基数排序时，如果运行时间为O(nk)，是否应该首先对输入进行某种操作以降低关键字长度(k)，否则平均关键字长度可能高达100log(n)（以10为底），这样我们将得到O(nlogn)，或者我可能误解了我正在阅读的基数排序描述。 - ejf071189

例如，这两种方法是否可以以某种方式结合起来，使n个元素被哈希到大小为n的表中，哈希函数使哈希值具有固定长度，而不管输入值如何，然后根据哈希值对哈希表执行基数排序？这似乎是绕弯路，但正如原问题陈述的更新中所指出的那样，搜索哈希集不适用于具有“最坏情况”O（1）运行时。 - ejf071189

@ejf071189：哈希值始终具有固定长度，通常存储在底层平台的本机字中，因此您可以假设在大多数计算机上使用64位。问题在于碰撞，由于您正在减少用于表示的空间，因此可能会共享相同哈希的多个整数：这是一种退化情况，应该假定为最坏情况分析，除非您可以证明它不可能发生（完美哈希）。 - Matthieu M.

Answer 4

#include <bits/stdc++.h>
using namespace std;
int main()
{
    unordered_map<string,int>m;
    int n,i;
    cin>>n;
    string a,b; // for storing numbers upto n^100
    for(i=0;i<n;i++)
    {
        cin>>a;
        m[a]=1;
    }
    for(i=0;i<n;i++)
    {
        cin>>b;
        if(m[b])
        {
            cout<<"Not disjoint";
            exit(0);
        }
    }
    cout<<"Disjoint";
    return 0;
}

时间复杂度：O(n) 辅助空间：O(n)

- Siddharth Verma

---

一个好的答案总是会包括解释为什么这样做可以解决问题，这样原帖作者和任何未来的读者都可以从中学习。 - Tyler2P

Answer 5

你可以使用基数排序算法，以n为基数对输入进行排序。

这将需要101次迭代遍历每个数组（因为输入数字的范围在0到n^100之间）。

一旦你排好了输入，你可以用O(n)的时间按照显而易见的方式进行比较。

注意：为了使基数排序在O(n)的时间内运行，你需要检查从输入数字中提取第k位（基数为n）是否是O(1)的。你可以通过(k-1)次除以n和一次模运算来实现。由于k最多为101，所以这是O(1)的。

---

^旁注 我注意到kennytm@在2010年也给出了类似的答案，但由于评论者指出“基数排序的时间复杂度为O（nk），其中n是键数，k是平均键长度。由于最大键值为n ^ 100，所以最大键长度将是100 log n。因此，这仍然是O（n log n），与所有最佳排序算法相同。”答案被删除。

请注意，该评论是错误的--最大键长为101，因为键是一系列数字的某个基数，并且不能用比特来衡量。

- Paul Hankin

Answer 6

老实说，我没想到从SO社区会得到这样的答案，但无妨。问题明确说明算法应该采用O(n)空间和时间复杂度，因此我们可以排除涉及哈希的算法，因为在最坏情况下，哈希不是O(n)。

现在我正在阅读一些文本，发现找到两个集合是否可缩小的问题可以归约为排序问题。这在研究许多算法的下界时非常标准。 来自S. K. BASU · 2013《设计方法与算法分析》一书的实际行。

在这里，作者清楚地声明，集合不相交显然是Ω(nlogn)。

- user18050317

---

数组中的值的上限（最大n^100）使您的论点无效。有限的范围允许在O(n)时间内进行排序--请参阅我的答案。 - Paul Hankin