找到序列的最长准常数子序列
Find longest quasi-constant sub-sequence of a sequence
今天早些时候我做了这个测试,我试图太聪明而遇到了障碍。不幸的是,我陷入了这种思维定势,浪费了太多时间,未能通过这部分测试。后来我解决了,但也许你们可以帮助我摆脱最初的困境。
问题定义:
给定一个由N个整数(均为正数)组成的无序非唯一序列A。 A的子序列是从A中去掉none个元素或全部元素得到的任意序列。序列的幅值是这个序列中最大元素和最小元素的差值。假设空子序列的振幅为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,returns 是数组 A 的最长准常数子序列的长度. 例如,给定上面概述的序列 A,函数应该 return 3,如解释的那样。
现在,我在 python 3.6 中使用没有 classes 的基于排序的方法解决了这个问题(我的代码在下面),但我最初不想这样做因为在大列表上排序可能非常慢。看起来这应该有一个相对简单的公式作为基于广度优先的树 class,但我无法正确理解。对此有什么想法吗?
我的 class-less 基于排序的解决方案:
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
我不知道 BFS 在这方面应该如何提供帮助。
为什么不简单地 运行 一次遍历序列并计算每个可能的 quasi-constant 子序列有多少个元素?
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))
打印:
3
符合预期。
解释:每个non-constant quasi-constant子序列由它包含的最大数唯一标识(只能有两个,取较大的)。现在,如果您有一个数字 s
,它可以对具有 s
或 s + 1
作为最大数的 quasi-constant 子序列做出贡献。因此,只需将 +1
添加到 s
和 s + 1
标识的子序列中。然后输出所有计数的最大值。
你不能比 O(n)
更快,因为你必须至少查看输入序列的每个条目一次。
正如 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)
部分。它可能会慢一点(在 per-item 的基础上)处理 O(k)
部分,因为它需要生成器表达式。 Andrey 的代码恰恰相反(O(n)
部分的 Python 代码运行速度较慢,O(k)
部分使用更快的内置 C 函数。由于 k
总是小于或等于 n
(如果序列有 lot 的重复值,可能会少很多),我的代码总体上更快。不过,这两种解决方案仍然是 O(n)
,并且都比对大输入进行排序要好得多。
今天早些时候我做了这个测试,我试图太聪明而遇到了障碍。不幸的是,我陷入了这种思维定势,浪费了太多时间,未能通过这部分测试。后来我解决了,但也许你们可以帮助我摆脱最初的困境。
问题定义:
给定一个由N个整数(均为正数)组成的无序非唯一序列A。 A的子序列是从A中去掉none个元素或全部元素得到的任意序列。序列的幅值是这个序列中最大元素和最小元素的差值。假设空子序列的振幅为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,returns 是数组 A 的最长准常数子序列的长度. 例如,给定上面概述的序列 A,函数应该 return 3,如解释的那样。
现在,我在 python 3.6 中使用没有 classes 的基于排序的方法解决了这个问题(我的代码在下面),但我最初不想这样做因为在大列表上排序可能非常慢。看起来这应该有一个相对简单的公式作为基于广度优先的树 class,但我无法正确理解。对此有什么想法吗?
我的 class-less 基于排序的解决方案:
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
我不知道 BFS 在这方面应该如何提供帮助。
为什么不简单地 运行 一次遍历序列并计算每个可能的 quasi-constant 子序列有多少个元素?
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))
打印:
3
符合预期。
解释:每个non-constant quasi-constant子序列由它包含的最大数唯一标识(只能有两个,取较大的)。现在,如果您有一个数字 s
,它可以对具有 s
或 s + 1
作为最大数的 quasi-constant 子序列做出贡献。因此,只需将 +1
添加到 s
和 s + 1
标识的子序列中。然后输出所有计数的最大值。
你不能比 O(n)
更快,因为你必须至少查看输入序列的每个条目一次。
正如 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)
部分。它可能会慢一点(在 per-item 的基础上)处理 O(k)
部分,因为它需要生成器表达式。 Andrey 的代码恰恰相反(O(n)
部分的 Python 代码运行速度较慢,O(k)
部分使用更快的内置 C 函数。由于 k
总是小于或等于 n
(如果序列有 lot 的重复值,可能会少很多),我的代码总体上更快。不过,这两种解决方案仍然是 O(n)
,并且都比对大输入进行排序要好得多。