查找包含所有元素的最短子数组

  • Z时代
  • 2024-01-10
  • 分类：问答

假设您有一个数字数组和另一组数字。您必须找到包含所有数字且最简单的最短子数组。

该数组可以有重复项，让我们假设数字集没有。它没有顺序-子数组可以按任意顺序包含数字集。

例如：

Array: 1 2 5 8 7 6 2 6 5 3 8 5
Numbers: 5 7

那么最短的子数组显然是Array[2:5]（Python表示法）。

另外，如果您出于某种原因想要避免对数组进行排序（在线算法），该怎么办？

回答：

回答：

我将写“ 右延伸” 表示将范围的右端点增加1，将“ 左收缩” 表示将范围的左端点增加1。此答案是Aasmund

Eldhuset答案的略有变化。此处的区别在于，一旦我们找到最小的j，使得[0，j]包含所有感兴趣的数字，此后，我们将仅考虑包含所有感兴趣的数字的范围。（有可能以此方式解释Aasmund的答案，但也有可能将其解释为允许由于左收缩而丢失一个有趣的数字，该算法的正确性尚待确定。）

基本思想是，对于每个位置j，我们都将找到终止于位置j的最短满足范围，因为我们知道终止于位置j-1的最短满足范围。

修复了基本情况下的故障。

基本情况：找到最小的j’，使[0，j’]包含所有有趣的数字。通过构造，不可能存在包含所有有趣数字的范围[0，k

<j’]，因此我们无需进一步担心它们。现在找到 最小的

最大i，使[i，j’]包含所有有趣的数字（即，保持j’固定）。这是在位置j’处结束的最小满足范围。

为了找到以任意位置j结尾的最小满足范围，我们可以将以j-1结尾的最小满足范围右扩展1个位置。该范围也可能包含所有有趣的数字，尽管它可能不是最小长度。

我们需要考虑的唯一操作是左收缩，它保留了包含所有有趣数字的属性。因此，在保持此属性的同时，应将范围的左端点尽可能提前。当无法再执行左收缩操作时，我们得到的最小长度满足范围以j结尾（因为进一步的左收缩显然不能使范围再次满足），我们完成了。

由于我们对每个最右边的位置j执行此操作，因此我们可以对所有最右边的位置取最小长度范围，以找到整体的最小值。这可以使用嵌套循环来完成，其中j在每个外循环循环中前进。显然，j前进了1

n倍。由于在任何时间点我们都只需要先前范围j的最佳范围的最左位置，因此我们可以将其存储在i中，并随即进行更新。i从0开始，始终在<= j <=

n，并且仅向前进1，这意味着它最多可以向n前进。i和j最多前进n次，这意味着该算法是线性时间。

在下面的伪代码中，我将两个阶段组合成一个循环。只有在达到所有有趣数字的阶段，我们才尝试收缩左侧：

# x[0..m-1] is the array of interesting numbers.
# Load them into a hash/dictionary:
For i from 0 to m-1:
    isInteresting[x[i]] = 1
i = 0
nDistinctInteresting = 0
minRange = infinity
For j from 0 to n-1:
    If count[a[j]] == 0 and isInteresting[a[j]]:
        nDistinctInteresting++
    count[a[j]]++
    If nDistinctInteresting == m:
        # We are in phase 2: contract the left side as far as possible
        While count[a[i]] > 1 or not isInteresting[a[i]]:
            count[a[i]]--
            i++
        If j - i < minRange:
            (minI, minJ) = (i, j)

count[]并且isInteresting[]是哈希/字典（如果涉及的数字很小，则为纯数组）。

以上是 查找包含所有元素的最短子数组 的全部内容， 来源链接： utcz.com/qa/422929.html

回到顶部