在 Python 中找到 LCM 至多 K 的数组的最长子序列
假设我们有一个由 n 个不同数字组成的数组 A 和另一个正整数 K,我们必须找到数组中最长的子序列,其中最小公倍数(LCM)最多为 K。然后返回 LCM 和子序列的长度-sequence,跟随所获得子序列的元素的索引(从0开始)。否则,返回-1。
所以,如果输入像 A = [3, 4, 5, 6], K = 20,那么输出将是 LCM = 12, Length = 3, Indexes = [0,1,3]
在线示例
让我们看看以下实现以获得更好的理解 -
from collections import defaultdictdef get_seq(A,k):
n = len(A)
my_dict = defaultdict(lambda:0)
for i in range(0, n):
my_dict[A[i]] += 1
count = [0] * (k + 1)
for key in my_dict:
if key <= k:
i = 1
while key * i <= k:
count[key * i] += my_dict[key]
i += 1
else:
break
lcm = 0
size = 0
for i in range(1, k + 1):
if count[i] > size:
size = count[i]
lcm = i
if lcm == 0:
print(-1)
else:
print("LCM = {0}, Length = {1}".format(lcm, size))
print("指标值: ", end = "")
for i in range(0, n):
if lcm % A[i] == 0:
print(i, end = " ")
k = 20
A = [3, 4, 5, 6]
get_seq(A,k)
输入
[3, 4, 5, 6] , 20输出结果
LCM = 12, Length = 3 指标值: 0 1 3
以上是 在 Python 中找到 LCM 至多 K 的数组的最长子序列 的全部内容, 来源链接: utcz.com/z/360919.html