在 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 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("指标值: ", 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

回到顶部