python - 找到序列的最长准常数子序列

Question

我今天早些时候进行了这个测试，但我太聪明了，遇到了障碍。不幸的是，我陷入了这种思维定势，浪费了太多时间，未能通过这部分测试。我后来解决了它，但也许你们都可以帮助我摆脱最初的困境。

问题定义:

给定一个由 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

Answer 1

正如 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 是输入中 distinct 值的数量(n 是输入中值的总数)。我的代码通过将序列交给用 C 实现的 Counter 构造函数来非常有效地处理 O(n) 部分。它可能会慢一点(在每个项目的基础上)来处理 O(k) 部分，因为它需要一个生成器表达式。 Andrey 的代码恰恰相反(它为 O(n) 部分运行较慢的 Python 代码，并为 O(k) 部分使用更快的内置 C 函数)。因为 k 总是小于或等于 n(如果序列有很多 lot 重复值，可能会少很多)，我的代码是总体上更快。不过，这两种解决方案的复杂度仍然是 O(n)，而且两者都应该比对大量输入进行排序要好得多。