在O(n)时间内进行排序交集

Question

让 S1 和 S2 为两组整数集合（它们不一定是不相交的）。我们知道 |S1|=|S2|=n (即每个集合都有 n 个整数)。每个集合存储在长度为 n 的数组中，其中其整数按升序排序。让 k ≥ 1 为一个整数。设计一种算法，在 O(n) 时间内找到 S1 ∩ S2 的前 k 小整数。

以下是我做出的方案: 1.创建一个名为 Intersection 的新数组。 2.对于 S1 中的每个 e，在 O(n) 时间内将 e 添加到哈希集中。 3.对于 S2 中的每个 e，在 O(n) 时间内检查 e 是否存在于哈希集中。 4.如果 e 存在于哈希集中，则将 e 添加到 Intersection 中。 5.一旦比较完成，使用计数排序在 O(n) 时间内对 Intersection 进行排序。 6.返回前 k 个整数。

因此 O(n) + O(n) + O(n) = O(n)。

您的方案基本正确，但需要注意的是在步骤 4 中添加元素的时间复杂度也应该是 O(n)，因为最坏情况下，所有元素都可能需要被添加到 Intersection 中。另外，在步骤 5 中使用计数排序是一种好的选择，但一般情况下都需要先判断是否需要使用计数排序来保证算法的时间复杂度为 O(n)。

- 101ldaniels

---

由于数组已按升序排序，因此可以使用双指针技术（几乎与归并排序中的合并过程相同）来完成此操作。 - Abhishek Bansal

哈希是杀鸡焉用牛刀，使用合并操作。 - user1196549

@Yves：合并就像用稍微小一点儿的锤子打苍蝇——它更好，但仍然是锤子 :-) 没有必要以任何方式组合列表，可以在O(n)时间和O(1)空间内完成。当然，除非您指的是“虚拟”合并操作，如我的答案所述，如果是这样，我提前道歉。 - paxdiablo

如果结果必须可用于进一步处理，则合并是必需的，绝不会过度。顺便说一句，只需将您的打印替换为追加，即可获得完全相同的算法。 - user1196549

@paxdiablo：确实，完全合并是愚蠢的，一旦找到k个元素就停止。 - user1196549

Answer 1

是的，你肯定在正确的轨道上，但实际上根本没有必要生成哈希表或额外的集合。由于你的两个集合已经排序了，所以你可以通过两个集合运行一个索引/指针，寻找共同元素。

例如，要从两个集合中找到第一个公共元素，请使用以下伪代码：

start at first index of both sets
while more elements in both sets, and current values are different:
    if set1 value is less than set2 value:
        advance set1 index
    else
        advance set2 index

在此之后，如果两个索引都没有移动到各自列表的最后一个元素之外，set1 index 将指向交集点。然后您只需在循环中使用该方法即可找到前三个 x 交集值。

以下是 Python 3 中的概念证明，它给出了两个列表（二的倍数和三的倍数）中的前三个数字。完整的交集将是 {0, 6, 12, 18, 24}，但您将看到它只提取其中的前三个：

# Create the two lists to be used for intersection.

set1 = [i * 2 for i in range(15)] ; print(set1) # doubles
set2 = [i * 3 for i in range(15)] ; print(set2) # trebles

idx1 = 0 ; count1 = len(set1)
idx2 = 0 ; count2 = len(set2)

# Only want first three.

need = 3
while need > 0:
    # Continue until we find next intersect or end of a list.

    while idx1 < count1 and idx2 < count2 and set1[idx1] != set2[idx2]:
        # Advance pointer of list with lowest value.

        if set1[idx1] < set2[idx2]:
            idx1 += 1
        else:
            idx2 += 1

    # Break if reached end of a list with no intersect.

    if idx1 >= count1 or idx2 >= count2:
        break

    # Otherwise print intersect and advance to next list candidate.

    print(set1[idx1]) ; need -= 1
    idx1 += 1 ; idx2 += 1

输出结果如预期：

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42]
0
6
12

如果您需要在最后生成列表而不只是打印交点，则只需在循环之前初始化一个空容器，然后将值附加到其中，而不是打印它。这样就有点像您提出的解决方案，但优点是不需要哈希表或排序。

- paxdiablo

Answer 2

创建两个数组，称其为arr1和arr2，大小为array_size，并按升序填充整数值。创建两个索引，称其为i和j，用于迭代arr1和arr2，并将它们初始化为0。比较每个数组的前两个值：如果arr1 [0]小于arr2 [0]，则增加i，否则如果arr1 [0]大于arr2 [0]则增加j，否则值相交，我们可以返回此值。一旦我们返回了k个相交值，就可以停止迭代。在最坏的情况下，如果这两组值之间没有相交，则这将是i+j，O（n），我们将不得不迭代到每个数组的末尾。

以下是bash中的解决方案：

#!/bin/bash
#-------------------------------------------------------------------------------
# Design an algorithm to find the k smallest integers in S1 ∩ S2 in O(n) time.
#-------------------------------------------------------------------------------

typeset -a arr1 arr2 arr_answer
typeset -i array_size=20 k=5

function populate_arrs {
    typeset -i counter=0

    while [[ ${counter} -lt ${array_size} ]]; do
        arr1[${counter}]=$((${counter} * 2))
        arr2[${counter}]=$((${counter} * 3))

        counter=${counter}+1
    done

    printf "%8s" "Set1: "; printf "%4d" ${arr1[*]}; printf "\n"
    printf "%8s" "Set2: "; printf "%4d" ${arr2[*]}; printf "\n\n"
}


function k_smallest_integers_main {
    populate_arrs

    typeset -i counter=0 i=0 j=0
    while [[ ${counter} -lt ${k} ]]; do
        if [[ ${arr1[${i}]} -eq ${arr2[${j}]} ]]; then
            arr_answer[${counter}]=${arr1[${i}]}
            counter=${counter}+1; i=${i}+1; j=${j}+1
        elif [[ ${arr1[${i}]} -lt ${arr2[${j}]} ]]; then
            i=${i}+1
        else
            j=${j}+1
        fi
    done

    printf "%8s" "Answer: "; printf "%4d" ${arr_answer[*]}; printf "\n"
}

k_smallest_integers_main

输出：

  Set1:    0   2   4   6   8  10  12  14  16  18  20  22  24  26  28  30  32  34  36  38
  Set2:    0   3   6   9  12  15  18  21  24  27  30  33  36  39  42  45  48  51  54  57

Answer:    0   6  12  18  24

- Jacek Trociński

---

只有一个小问题，O(i+j) 似乎显示了对复杂度分析的基本误解。最坏情况下只是 O(n)。更准确的做法是仅说明最坏情况是 i + j 步骤，而不是引入大 O 符号。 - paxdiablo

@paxdiablo 谢谢，已纠正，不过类似 O(m+n) 的复杂度难道不是可以简化为 O(n) 吗？还是我漏了什么信息？ - Jacek Trociński