algorithm - 定义重叠元素或不包含在子集中的元素

Question

我想检查哪种策略最有效地计算下面描述的问题

我有一组 Q 和两个子集 L 和 R。我有三种情况。

1) L ∩ R != 0。在这种情况下，我想获取重叠元素的数组。在下面的示例中，结果集将为 R = {4, 5}。

  Q = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  L = {0, 1, 2, 3, 4, 5, *, *, *, *}
  R = {*, *, *, *, 4, 5, 6, 7, 8, 9}

2) L ∩ R = 0。在这种情况下，我想得到 Q\(L ∪ R)。在下面的示例中，结果集将为 R = {4, 5, 6}。

  Q = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  L = {0, 1, 2, 3, *, *, *, *, *, *}
  R = {*, *, *, *, *, *, *, 7, 8, 9}

3) Q\(L ∪ R) = 0。在这种情况下，我想得到他们找到彼此的索引。在下面的示例中，索引将为 4。

  Q = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  L = {0, 1, 2, 3, 4, *, *, *, *, *}
  R = {*, *, *, *, *, 5, 6, 7, 8, 9}

Answer 1

如果 L ∩ R != 0，那么我会:

选择两个最小的数组，比较它们以找出共同的元素。

这将为您节省一个循环，并且会导致 O(n²)，而不是原始的 O(n³)。

在另一种情况下，我看不出如何避免访问每个数组的每个元素。

---

注意:如果您使用数据结构，sush HashMap ，那么这两种情况都将在线性时间内解决。