我們有一個大小為 n-1 的未排序陣列，其中包含從 1 到 n 的數字，不包括一個數字。我們需要找到那個丟失的號碼。
就像我們有輸入 [8,1,5,4,2,7,6]，那么它應該回傳 3。
我得到的約束：
嘗試在左側收集較小的患者編號，在右側收集較大的患者編號。在您的解決方案中，您必須使用 QuickSort 使用的磁區演算法（不使用磁區和遞回的解決方案，例如從直到 n 的整數總和中減去 A 中元素的總和將不是有效答案）。
這怎么可能？
uj5u.com熱心網友回復：
這個問題可以用一個很像quickselect的演算法來解決：
這個想法是像使用快速選擇（和快速排序）一樣對輸入陣列進行磁區。那時我們知道樞軸元素出現在對陣列進行排序時的位置。有兩種可能：
樞軸的值比它所在的索引大 2。例如，如果我們有 [1, 3, 4] 并且中間元素是樞軸，那么實際上值 3 比它所在的索引 (1) 多兩個。
在這種情況下，我們可以得出缺失值小于樞軸值的結論，我們可以在左磁區中遞回地重復該程序
樞軸的值比它所在的索引大 1。例如，如果我們有 [1, 2, 4] 并且中間元素是樞軸，那么實際上值 2 比它所在的索引 (1) 大一。
在這種情況下，我們可以得出缺失值大于樞軸值的結論，我們可以在右磁區中遞回地重復該程序
這是該演算法在 Python 代碼中的實作：
from random import randint
def partition(arr, l, r):
i = randint(l, r) # choose pivot randomly
arr[i], arr[r] = arr[r], arr[i] # swap it out of the way
x = arr[r] # get pivot value
i = l
for j in range(l, r):
if arr[j] <= x:
arr[i], arr[j] = arr[j], arr[i] # swap
i = 1
# swap pivot element into its final place
arr[i], arr[r] = arr[r], arr[i]
return i
def findmissing(arr, l, r):
if l > r: # base case
return arr[r] 1 if r >= 0 else 1
pivotindex = partition(arr, l, r)
if arr[pivotindex] == pivotindex 2: # missing element must be on the left
return findmissing(arr, l, pivotindex - 1)
else: # missing element is on the right
return findmissing(arr, pivotindex 1, r)
# Demo run
arr = [8,1,5,4,2,7,6]
print(findmissing(arr, 0, len(arr)-1)) # 3
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/531674.html
下一篇：有人能解釋一下這個leetcodejavascript問題中的“current.next”和“current.val”是什么意思嗎？