在 Python 中查找数组中 LCM 最多为 K 的最长子序列

pythonserver side programmingprogramming更新于 2025/9/30 10:52:17

假设我们有一个包含 n 个不同数字的数组 A 和另一个正整数 K,我们必须在数组中找到最小公倍数 (LCM) 最多为 K 的最长子序列。然后返回 LCM 和子序列的长度,按照获得的子序列元素的索引(从 0 开始)。否则,返回 -1。

因此,如果输入为 A = [3, 4, 5, 6],K = 20,则输出将是 LCM = 12、Length = 3、Indexes = [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

  • 对于 i,范围为 1 到 k + 1,执行

    • 如果 count[i] > size,然后

      • size := count[i]

      • lcm := i

  • 如果 lcm 与 0 相同,则

    • 返回 -1

  • 否则,

    • 显示 lcm 和 size

    • 对于 0 到 n 范围内的 i,执行

      • 如果 lcm mod 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

相关文章


有用资源