数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 Python 查找数组中 LCM 最多为 K 的最长子序列
假设我们有一个包含 n 个不同数字的数组 A 和另一个正整数 K，我们需要找到数组中具有最小公倍数 (LCM) 最多为 K 的最长子序列。然后返回 LCM 和子序列的长度，以及获得的子序列元素的索引（从 0 开始）。否则，返回 -1。
因此，如果输入类似于 A = [3, 4, 5, 6]，K = 20，则输出将是 LCM = 12，长度 = 3，索引 = [0,1,3]
为了解决这个问题，我们将遵循以下步骤：
n := A 的大小
my_dict := 一个映射
从 0 到 n 循环 i，执行：
my_dict[A[i]] := my_dict[A[i]] + 1
count := 一个大小为 (k + 1) 并填充 0 的数组
对于 my_dict 中的每个键，执行：
如果 key <= k，则：
i := 1
当 key * i <= k 时，执行：
count[key * i] := count[key * i] + my_dict[key]
i := i + 1
否则：
退出循环
lcm := 0，size := 0
从 1 到 k + 1 循环 i，执行：
如果 count[i] > size，则：
size := count[i]
lcm := i
如果 lcm 等于 0，则：
返回 -1
否则：
显示 lcm 和 size
从 0 到 n 循环 i，执行：
如果 lcm 模 A[i] 等于 0，则：
显示 i
示例
让我们看看以下实现，以更好地理解：
from collections import defaultdict
def 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("Index values: ", 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 Index values: 0 1 3
更新于: 2020年8月20日
413 次查看
广告