我之前也問過類似的問題，但這次不同。
由于我們的陣列只包含兩個元素，我們不妨將其設定為 1 和 -1，其中 1 位于陣列的左側，-1 位于陣列的右側：
[1,...,1,1,-1,-1,...,-1]
1和-1同時存在，1和-1的個數不一定相同。此外，1 和 -1 的數字都非常大。
然后，將 1 和 -1 之間的邊界定義為最接近1的 -1的索引。例如，對于以下陣列：
[1,1,1,-1,-1,-1,-1]
它的邊界是3。
現在，對于陣列中的每個數字，我用一個設備覆寫它，你必須解鎖它才能看到其中的數字。
我想嘗試解鎖覆寫 1 的盡可能少的設備，因為看到“1”比看到“-1”需要更長的時間。而且我也想盡可能地減少我的時間成本。
如何搜索以盡快獲得邊界？
uj5u.com熱心網友回復：
這個問題很像“雞蛋掉落”問題，但是錯誤的猜測有很大的固定成本（100），而正確的猜測有很小的成本（1）。
假設 E(n) 是在陣列中找到最右邊的 1 的索引（或找到陣列全為 -1）的（最佳）預期成本，假設邊界的每個可能位置都是同樣可能的。如果陣列全為 -1，則定義最右邊 1 的索引為 -1。
如果您選擇查看索引 i 處的陣列元素，那么它的概率為 -1，概率i/(n 1)為 1 (n-i 1)/(n 1)。
因此，如果您查看陣列元素 i，您尋找邊界的預期成本是(1 E(i)) * i/(n 1) (100 E(n-i-1)) * (n-i 1)/(n 1).
因此 E(n) = min((1 E(i)) * i/(n 1) (100 E(n-i-1)) * (n-i 1)/(n 1), i=0..n-1)
對于每個 n，i最小化方程的 是要查看該長度陣列的最佳陣列元素。
我認為您無法決議地求解這些方程，但您可以在 O(n^2) 時間內通過動態規劃求解它們。
該解決方案看起來像是對大 n 的非常偏斜的二進制搜索。對于較小的 n，它會偏斜很多，以至于它將是從右側開始的遍歷。
uj5u.com熱心網友回復：
如果我是對的，最小化成本預期的策略是在有利于 -1 結果的區間的一小部分繪制，與成本成反比。因此，不要選擇中間索引，而是選擇正確的百分位數。
但這仍然對應于對數漸近復雜度。
對于最壞的情況，您可能無能為力。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/410213.html
標籤：
上一篇：二叉樹每一層的最大值