資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告