想象一下，有一個整數陣列，但不允許您訪問任何值（所以沒有Arr[i] > Arr[i 1]或其他什么）。區分整數的唯一方法是使用query()函式：該函式將元素子集作為輸入并回傳該子集中唯一整數的數量。目標是根據它們的值將整數分成組——同一組中的整數應該具有相同的值，而不同組中的整數具有不同的值。問題 - 代碼必須是 O(nlog(n))，或者換句話說，query() 函式只能被呼叫 O(nlog(n)) 次。
我花了幾個小時在 Python 中優化不同的演算法，但所有演算法都是 O(n^2)。作為參考，這是我開始的代碼：
n = 100
querycalls = 0
secretarray = [random.randint(0, n-1) for i in range(n)]
def query(items):
global querycalls
querycalls = 1
return len(set(items))
groups = []
secretarray生成一個巨大的亂數字串列，長度為n。querycalls跟蹤呼叫了多少函式。groups是結果的去處。
我做的第一件事是嘗試創建一個基于合并排序的演算法（將陣列拆分，然后根據 query() 值合并），但我永遠無法將其降低到 O(n^2) 以下。
uj5u.com熱心網友回復：
假設您有一個元素x和一個不同元素的陣列，A = [x0, x1, ..., x_{k-1}]并且想知道 是否x相當于陣列中的某個元素，如果是，則是哪個元素。
你可以做的是一個簡單的遞回（讓我們稱之為check-eq）：
- 檢查是否
query([x, A]) == k 1。如果是，那么您知道這x與A. - 否則，您知道這
x等效于 的某個元素A。讓A1 = A[:k/2], A2 = A[k/2 1:]. 如果query([x, A1]) == len(A1)，那么你知道它x等價于 in 的某個元素A1，所以遞回 inA1。否則在A2.
這個遞回最多需要O(logk)幾步。現在，讓我們的初始陣列為T = [x0, x1, ..., x_{n-1}]。A將是一組元素的“代表”陣列。你要做的是首先取A = [x0]和x = x1。現在用于check-eq查看是否x1與x0. 如果沒有，那么讓A = [x0, x1]. 否則什么都不做。繼續x = x2。你可以看到它是怎么回事。
復雜性當然是O(nlogn)，因為check-eq被呼叫的n-1次數和每次呼叫都需要O(logn)時間。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350532.html
上一篇：帶有扭曲演算法的BFS最短路徑