找到一个序列中最长的准恒定子序列

Question

找到一个序列中最长的准恒定子序列

pythontreesubsequence

5

我今天早些时候参加了这个测试，试图聪明过头导致卡住了。不幸的是，我陷入了这种思维困境，浪费了太多时间，在测试的这一部分失败了。之后我解决了它，但希望你们可以帮助我摆脱最初的困境。

问题定义：

给定一个由N个整数组成的未排序、非唯一序列A（均为正数）。来自A的子序列是通过从A中删除零个或多个元素获得的任意序列。序列的振幅是该序列中最大元素与最小元素之间的差值。空子序列的振幅被认为是0。

例如，考虑由六个元素组成的序列A，其中：

A[0] = 1
A[1] = 7
A[2] = 6
A[3] = 2
A[4] = 6
A[5] = 4

如果一个数组A的子序列幅度不超过1，则称其为准恒定子序列。在上面的示例中，子序列[1,2]、[6,6]和[6,6,7]是准恒定的。子序列[6,6,7]是A中可能的最长准恒定子序列。

现在，找到一个解决方案，给定由N个整数组成的非空零索引数组A，返回数组A的最长准恒定子序列的长度。例如，对于上述序列A，函数应该返回3。

我使用没有类的基于排序的方法在Python 3.6中解决了这个问题（下面是我的代码），但我最初并不想这样做，因为在大型列表上进行排序可能会非常慢。它似乎应该有一个相对简单的广度优先基于树的类形式，但我无法做到。你有什么想法吗？

def amp(sub_list):
    if len(sub_list) <2:
        return 0
    else:
        return max(sub_list) - min(sub_list)

def solution(A):
    A.sort()
    longest = 0
    idxStart = 0
    idxEnd = idxStart + 1
    while idxEnd <= len(A):
        tmp = A[idxStart:idxEnd]
        if amp(tmp) < 2:
            idxEnd += 1
            if len(tmp) > longest:
                longest = len(tmp)
        else:
            idxStart = idxEnd
            idxEnd = idxStart + 1
    return longest

- NichD

你说“在大型列表上排序可能非常慢”，但排序具有时间复杂度为O(n log n)，并且已经高度优化。大多数树算法具有相同的时间复杂度，但并未进行优化。你为什么认为树算法比基于排序的算法更好呢？（一个好的基于排序的解决方案在排序后是O(n)的。） - Rory Daulton

我想你说得很有道理。看来我确实过度思考了这个问题。 - NichD

2个回答

5

正如Andrey Tyukin指出的那样，你可以在O(n)的时间内解决这个问题，这比排序或任何基于树的解决方案获得的O(n log n)时间更好。技巧是使用字典来计算输入中每个数字的出现次数，并使用计数来确定最长子序列。

我有一个类似的想法，但我考虑了一个略微不同的实现。经过一些测试，看起来我的方法要快得多，所以我将其发布为我的答案。它非常简短！

from collections import Counter

def solution(seq):
    if not seq:     # special case for empty input sequence
        return 0
    counts = Counter(seq)
    return max(counts[x] + counts[x+1] for x in counts)

我怀疑这比Andrey的解决方案更快，因为我们两个解决方案的运行时间都需要O(n) + O(k)时间，其中k是输入中不同值的数量（而n是输入中的总值）。我的代码通过将序列交给用C实现的Counter构造函数来高效地处理O(n)部分。处理O(k)部分可能会稍微慢一些（在每个项的基础上），因为它需要一个生成器表达式。Andrey的代码则相反（它运行较慢的Python代码来处理O(n)部分，并使用更快的内置C函数来处理O(k)部分）。由于k始终小于或等于n（如果序列有很多重复值，则可能远小于n），所以我的代码整体上更快。两种解决方案仍然是O(n)，对于大型输入，两者都应该比排序要好得多。

- Blckknght

这是一份详细的分析，并且再次感谢您提供“Counter”的提示！ - Andrey Tyukin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andrey Tyukin · Accepted Answer

我不知道BFS在这里应该如何帮助。

为什么不直接遍历一次序列，并计算每个可能的准恒定子序列将会有多少个元素？

from collections import defaultdict

def longestQuasiConstantSubseqLength(seq):
  d = defaultdict(int)
  for s in seq:
    d[s] += 1
    d[s+1] += 1
  return max(d.values() or [0])

s = [1,7,6,2,6,4]

print(longestQuasiConstantSubseqLength(s))

输出:

如预期。

解释：每个非常数准常子序列都可通过它包含的最大值（最多只有两个，取较大者）唯一确定。现在，如果你有一个数字 s ，它可以要么对具有 s 或 s+1 作为最大值的准常子序列做出贡献。所以，只需将 +1 添加到由 s 和 s+1 确定的子序列中。然后输出所有计数的最大值。

你不能使速度比 O(n) 更快，因为你必须至少查看输入序列的每个条目一次。