A, B兩個長度為 的排序陣列n,m (n <= m)，并且k給(k >= log n)定。
log (nm)我們可以在這兩個陣列的聯合中找到最小k-th的數字。
我有一個解決方案在這里的問題 2中，但我的挑戰是為什么兩個給定條件“(n <= m)”和“k >= log n”不影響這個演算法？
uj5u.com熱心網友回復：
第一個假設：
n <= m是一個“不失一般性”的假設。如果 n >= m，那么只需在你的腦海中交換 A 和 B。即使不需要，他們也包括了這個假設，因為他們覺得做出這個假設是“自由的”。第二個假設：找到第
kth 最小元素的簡單演算法是同時迭代 A 和 B，在具有兩者中較小元素的陣列中前進。這與從mergesort 運行“Merge”函式完全一樣，但在合并前k 個元素后停止。復雜度為 O(k)。他們希望你找到一個更復雜的演算法，所以他們通過宣告 k >= log(n) “排除”了這個演算法，這意味著復雜度 O(k) 永遠不會比 O(log(n)) 好。從技術上講，如果他們想徹底排除這個演算法，他們也應該宣告k <= n m - log(n)，否則你可以從最后運行“合并”函式：合并 n mk 個最大元素，然后回傳第n m-kth 個最大元素，
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/462128.html