查找包含所有元素的最短子阵列 [英] Find shortest subarray containing all elements

问题描述

假设有数字数组，和另一组数字。你必须找到包含最小的复杂程度所有号码的最短子阵列。

Suppose you have an array of numbers, and another set of numbers. You have to find the shortest subarray containing all numbers with minimal complexity.

该阵列可以有重复，我们假设组数字没有。这不是命 - 子数组可能包含定数以任意顺序。

The array can have duplicates, and let's assume the set of numbers does not. It's not ordered - the subarray may contain the set of number in any order.

例如：

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

然后在最短子阵列显然是数组[2：5]。（蟒蛇符号）

此外，你会怎么做，如果你想避免排序阵列出于某种原因（一拉在线算法）？

Also, what would you do if you want to avoid sorting the array for some reason (a la online algorithms)?

推荐答案

我会写的右键扩展的意味增加1一系列正确的终点，而左收缩的意味增加1一系列的左端点这个答案是一个轻微的变化<一href="http://stackoverflow.com/questions/5447561/find-shortest-subarray-containing-all-elements/5447601#5447601">Aasmund Aldhuset的回答。这里的不同之处在于，一旦我们找到最小Ĵ使得[0，j]的包含所有有趣的数字，我们此后只考虑包含所有有趣的数字范围。 （这是可能的跨preT Aasmund的回答这种方式，但它也可以跨preT它允许一个有趣的数字是由于左缩失去了 - 一个算法的正确性还有待成立。）

Proof of a linear-time solution

I will write right-extension to mean increasing the right endpoint of a range by 1, and left-contraction to mean increasing the left endpoint of a range by 1. This answer is a slight variation of Aasmund Aldhuset's answer. The difference here is that once we find the smallest j such that [0, j] contains all interesting numbers, we thereafter consider only ranges that contain all interesting numbers. (It's possible to interpret Aasmund's answer this way, but it's also possible to interpret it as allowing a single interesting number to be lost due to a left-contraction -- an algorithm whose correctness has yet to be established.)

其基本思想是，对于每个位置j，我们会发现最短的满意区间在位置j结束，因为我们知道最短的满意区间在位置j-1结束。

The basic idea is that for each position j, we will find the shortest satisfying range ending at position j, given that we know the shortest satisfying range ending at position j-1.

编辑：修正了一个小故障的基本情况

Fixed a glitch in the base case.

基本情况：找到最小的J'，使得[0，J']包含所有有趣的数字。通过构造，就不可能有范围[0，K＆其中; J']包含所有有趣的数字，所以我们不需要再担心它们。现在，找到最小的我，这样[I，J']包含所有有趣的数字（即持有J'固定）。这是最小的满意区间在位置j'结尾。

Base case: Find the smallest j' such that [0, j'] contains all interesting numbers. By construction, there can be no ranges [0, k < j'] that contain all interesting numbers so we don't need to worry about them further. Now find the smallest i such that [i, j'] contains all interesting numbers (i.e. hold j' fixed). This is the smallest satisfying range ending at position j'.

要找到最小的满意范围内的任意位置j结束，我们可以通过1位右延伸最小的满意区间在位置j-1结束。这个范围必然还包含所有有趣的数字，尽管它可能不是最小长度。 ，我们已经知道这是一个令人满意的范围内，这一事实意味着我们不必担心扩大范围的倒退到左边，因为这只能增加在其最小长度的范围（即使解决方案更糟糕的）。我们需要考虑的操作只有左收缩，preserve包含所有有趣的数字财产。因此范围的左端点应尽可能同时此属性拥有先进的。当没有更多的左的收缩可以执行，我们有最小的长度满意区间在Ĵ结束（因为进一步的左收缩显然不能让再满足范围），我们正在做的。

To find the smallest satisfying range ending at any arbitrary position j, we can right-extend the smallest satisfying range ending at position j-1 by 1 position. This range will necessarily also contain all interesting numbers, though it may not be minimal-length. The fact that we already know this is a satisfying range means that we don't have to worry about extending the range "backwards" to the left, since that can only increase the range over its minimal length (i.e. make the solution worse). The only operations we need to consider are left-contractions that preserve the property of containing all interesting numbers. So the left endpoint of the range should be advanced as far as possible while this property holds. When no more left-contractions can be performed, we have the minimal-length satisfying range ending at j (since further left-contractions clearly cannot make the range satisfying again) and we are done.

由于我们执行此为每个最右边的位置j，我们可以采取最小长度范围的所有最右边的位置，找到整体的最小值。这可以使用一个嵌套循环，其中在每个外环除循环j前进来完成。显然Ĵ垫款1 n次。因为在任何时候，我们只有永远需要的最佳范围j的previous值最左边的位置，我们可以存储这我，只是更新它，因为我们走。我从0开始，在任何时候和LT = J＆LT; = n，且只有永远向上的获得是1，这意味着它可以提前至多N次。既i和j提前最多n倍，这意味着该算法是线性时间的

Since we perform this for each rightmost position j, we can take the minimum-length range over all rightmost positions to find the overall minimum. This can be done using a nested loop in which j advances on each outer loop cycle. Clearly j advances by 1 n times. Since at any point in time we only ever need the leftmost position of the best range for the previous value of j, we can store this in i and just update it as we go. i starts at 0, is at all times <= j <= n, and only ever advances upwards by 1, meaning it can advance at most n times. Both i and j advance at most n times, meaning that the algorithm is linear-time.

在下面的伪code，我结合这两个阶段为一个循环。我们只能尽量收缩左侧，如果我们已经达到了让所有有趣的数字的阶段：

In the following pseudo-code, I've combined both phases into a single loop. We only try to contract the left side if we have reached the stage of having all interesting numbers:

# 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)

计数[] 和 isInteresting [] 的散列/字典（或纯数组，如果所涉及的人数不多）。

count[] and isInteresting[] are hashes/dictionaries (or plain arrays if the numbers involved are small).

这篇关于查找包含所有元素的最短子阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！