資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 Python 中查詢最長雙調序列，其中遞增和遞減部分來自兩個不同的陣列
假設我們有兩個陣列；我們必須找到最長的可能的雙調序列，以便遞增部分應該來自第一個陣列並且應該是第一個陣列的子序列。類似地，遞減部分必須來自第二個陣列並且是第二個陣列的子序列。
因此，如果輸入類似於 A = [2, 6, 3, 5, 4, 6]，B = [9, 7, 5, 8, 4, 3]，則輸出將為 [2, 3, 4, 6, 9, 7, 5, 4, 3]
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 index_ceiling()。這將接收 arr、T、left、right、key
當 right - left > 1 時，執行
mid := left +(right - left) / 2;
如果 arr[T[mid]] >= key，則
right := mid
否則，
left := mid
返回 right
定義一個函式 long_inc_seq()。這將接收 A
n := A 的大小
tails_idx := 一個大小為 n 的陣列，填充為 0
prev_idx := 一個大小為 n 的陣列，填充為 -1
length := 1
對於 i 的範圍從 1 到 n，執行
如果 A[i] < A[tails_idx[0]]，則
tails_idx[0] := i
否則當 A[i] > A[tails_idx[length - 1]] 時，則
prev_idx[i] := tails_idx[length - 1]
tails_idx[length] := i
length := length + 1
否則，
pos := index_ceiling(A, tails_idx, -1, length - 1, A[i])
prev_idx[i] := tails_idx[pos - 1]
tails_idx[pos] := i
i := tails_idx[length - 1]
當 i >= 0 時，執行
將 A[i] 插入到答案的末尾
i := prev_idx[i]
從主方法中，執行以下操作 -
n1 := A 的大小，n2 := B 的大小
long_inc_seq(A)
answer := 反轉答案
B := 反轉 B
long_inc_seq(B)
返回 answer
示例
讓我們看看以下實現以獲得更好的理解 -
answer = [] def index_ceiling(arr,T, left,right, key): while (right - left > 1): mid = left + (right - left) // 2; if (arr[T[mid]] >= key): right = mid else: left = mid return right def long_inc_seq(A): n = len(A) tails_idx = [0]*(n) prev_idx = [-1]*(n) length = 1 for i in range(1, n): if (A[i] < A[tails_idx[0]]): tails_idx[0] = i elif (A[i] > A[tails_idx[length - 1]]): prev_idx[i] = tails_idx[length - 1] tails_idx[length] = i length += 1 else: pos = index_ceiling(A, tails_idx, -1, length - 1, A[i]) prev_idx[i] = tails_idx[pos - 1] tails_idx[pos] = i i = tails_idx[length - 1] while(i >= 0): answer.append(A[i]) i = prev_idx[i] def long_bitonic(A,B): n1 = len(A) n2 = len(B) global answer long_inc_seq(A) answer = answer[::-1] B = B[::-1] long_inc_seq(B) A = [2, 6, 3, 5, 4, 6] B = [9, 7, 5, 8, 4, 3] long_bitonic(A,B) print(answer)
輸入
[2, 6, 3, 5, 4, 6], [9, 7, 5, 8, 4, 3]
輸出
[2, 3, 4, 6, 9, 7, 5, 4, 3]
91 次檢視
