代码之家 › 专栏 › 技术社区 › callum

如何识别数组中与给定序列不匹配的元素?

search arrays python

callum · 技术社区 · 1 年前

考虑给定的序列 sequence = [1, 1, 0] 。

贯穿序列的数组示例如下 [1, 1, 0, 1, 1, 0, 1, 1, 0] 。

我有一个数组,除了一些异常值外,它始终遵循序列。这种数组的一个例子是 [1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0] 在该数组中,作为异常值的元素位于第6和第16索引处。如果这些异常值被去除,数组将始终遵循序列。

我想写一个python代码,打印数组中异常值的索引。假设该数组只有0和1。

代码应如下所示:

sequence = [1, 1, 0]
array_with_outliers = [...] //given
//code to identify outliers
print(indices_of_outliers)

我失败的尝试

我试图将array_with_outliers分解为3个元素的块。然后,我对这些块进行迭代,看看它们是否与序列匹配。如果区块n与序列不匹配,我将元素弹出到array_with_outliers中的索引3(n-1),并再次对array_with_outliers进行区块划分,递归地执行相同的过程,直到array_with-outliers为空。然而,代码效率太低,我的笔记本电脑无法运行它。

我还尝试迭代array_with_outliers,看看每个元素是否与基于序列的预期值匹配。我根据指数和迄今为止发现的异常值数量计算了预期值。然而,问题是我单独将每个元素与其期望值进行比较,而不是将块作为一个整体进行比较,这造成了重叠的问题。

2 回复 | 直到 1 年前

Samwise 1 年前

您可以在线性时间内做到这一点,只需遍历数组,跳过匹配的块,并一次累积一个不匹配的索引,直到找到下一个匹配的块。

def find_outliers(needle: list[int], haystack: list[int]) -> list[int]:
    """Find indices in haystack where
    the sequence of repeated needles is broken."""
    outliers: list[int] = []
    i = 0
    while i < len(haystack):
        if haystack[i:i+len(needle)] == needle:
            i += len(needle)
        else:
            outliers.append(i)
            i += 1
    return outliers

assert not find_outliers(
    [1, 1, 0],
    [1, 1, 0, 1, 1, 0, 1, 1, 0]
)

assert find_outliers(
    [1, 1, 0],
    [1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0]
) == [6, 16]

Kelly Bundy 1 年前

使用 bytes.find 以查找序列的出现。我的 i 告诉下一次发生的位置预期启动和 j 告诉它在哪里 事实上 启动。(框架大多抄袭自Samwise。)

def find_outliers(needle: list[int], haystack: list[int]) -> list[int]:
    """Find indices in haystack where
    the sequence of repeated needles is broken."""
    outliers: list[int] = []
    i = 0
    needle = bytes(needle)
    find = bytes(haystack).find
    while (j := find(needle, i)) != -1:
        outliers += range(i, j)
        i = j + len(needle)
    outliers += range(i, len(haystack))
    return outliers

assert not find_outliers(
    [1, 1, 0],
    [1, 1, 0, 1, 1, 0, 1, 1, 0]
)

assert find_outliers(
    [1, 1, 0],
    [1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0]
) == [6, 16]

assert find_outliers(
    [1, 1, 0],
    [1, 1, 0, 1, 1]
) == [3, 4]

Attempt This Online!