我在在線面試中遇到了這個問題。我無法讓所有的測驗用例都通過。我正在尋找如何解決它。
我們有兩個陣列A和B，N每個陣列由整數組成。我們希望將它們合并到陣列中C，使得對于每個索引K（從 0 到 N - 1），C[K]可以是A[K]或B[K]。例如，陣列A = [1, 2, 4, 3]和B = [1, 3, 2, 3]可以通過以下任何一種方式進行合并：
[1,2,4,3] [1,3,4,3] [1,2,2,3] [1,3,2,3]
我們的目標是使C不存在的最小正整數C盡可能小。在我們的例子中的安排，這個值是5，2，4和4分別。所以，我們的解決方案是第二種安排，結果是2。
更多例子：
A = [1, 2, 4, 3]和B = [1, 3, 2, 3]，答案：2A = [3, 2, 1, 6, 5]和B = [4, 2, 1, 3, 3]，答案：3因為我們可以創建C = [4, 2, 1, 6, 5]A = [1, 2]和B = [1, 2], 答案：3因為C = [1, 2]是唯一可能的安排。
約束：
- 輸入陣列大小，
1 < N < 10^5 0 < A[i], B[i] <= 10^5- 輸入陣列大小相同。
我的方法：
我貪婪地比較了這兩個陣列，并在名為 C 的新向量中推送了兩個元素中較大的元素。然后對其進行迭代以找到第一個丟失的正元素。我想將兩個元素的最大值推到答案的邏輯存在一些缺陷。一些隱藏的測驗用例失敗了。
偽代碼：
input A,B
for i = 0 to N-1:
C[i] = max(A[i], B[i])
sort(C)
h = 0
for i = 0 to N-1:
if C[i] - h > 1:
return h 1
h = C[i]
return h 1
uj5u.com熱心網友回復：
好吧，我將通過為您的方法提供一個反例來開始我的回答。假設輸入是：
A = [3, 2, 1, 6, 5, 3] and B = [4, 2, 1, 3, 3, 3]
根據您的方法，C將創建為：[4, 2, 1, 6, 5, 3]，因此，答案將是7
但可能C是：[3, 2, 1, 6, 5, 3]，這導致答案是4。請注意，對于C[0]，我們取了 的較低者A[0] and B[0]。
我認為這個案子應該敲響了警鐘。這是我的方法：
- 因為我們有
0 < A[i], B[i] <= 10^5，所以創建一個輔助陣列，比如H大小10^5 1并將其初始化為zeroes。 - 現在，迭代
A and B，尋找那些值 whereA[i] == B[i]，對于那些值，設定H[A[i]] = 1 - 再次迭代
A and B。如果H[A[i]] == 1 or H[B[i]] == 1，繼續。否則，設定H[max(A[i], B[i])] = 1。 - 現在，
H從索引 1 開始迭代。的index，你覺得你的1日0是你的答案。
uj5u.com熱心網友回復：
從第二個例子來看，它不應該回傳 1 嗎？因為我們可以形成陣列C = [4, 3, 3, 6, 5]也許我缺少一個條件？
更新
是的，對不起，我誤解了這個程序。所以，你的做法似乎是正確的：比較A[i]與B[i]和選擇較大的一個，并將其分配給C[i]。
現在，要找到不在 中的最小數字C，在創建C陣列之后，您需要找到一種方法來查找所有現有的“間隙”（間隙，我的意思是指具有兩個數字 x 和 y 的間隔，它們相差至少為 2：例如 [2,4] 或 [110, 290]。您需要找到 x 具有最小值的間隙。然后，答案就是 x 1。
此外，您需要考慮完全沒有間隙的情況，如第三個示例。
例如，偽代碼如下所示：
// If there is at least one gap
// find all the gaps
C.sort() // sort C to ascending order
// iterate C to find the first gap. And this gap will surely have the smallest x.
ans = min_x 1;
// If there is no gap
if (min_element != 1) then ans = min_element - 1
else ans = max_element 1
uj5u.com熱心網友回復：
編輯 我洗掉了代碼，因為它與 Gaurav 存在相同的問題
@vish4071 讓我意識到，我的代碼有一些問題/與作者的問題相同。但是我想我現在發現了上面代碼的問題，我將用一個例子來演示它：
A = [1,2,3,3], B = [1,2,1,4]
使用上面的代碼，我們將得到 5 作為最小元素。然而我們在C中的smalles元素應該是3。為什么？？看：
C = [1,2,1,4]
將較大元素推送到陣列 C 的邏輯有什么缺陷？每當我們比較兩個數字時，我們必須檢查較小的數字是否已經在我們的陣列 C 中。如果是 -> 我們應該添加較小的數字，因為它不會增加我們的最小元素。（這里 idx 2 是重要的）
uj5u.com熱心網友回復：
從問題陳述中，尚不清楚
a)是否需要最小結果，或者
1) 值C 的一個可能序列- 下文將忽略
對于作為潛在結果 (0 < v ≤ N) 的值v，應該有一個記分板（長度 N 或 N 1 ）。
每一個不超過 N 的數字都開始一個不在C 中的可能的最小數字。
無法避免的數字是A [k] 等于B [k]。
如果消除大于任一的數字，結果不會改變：
- 步行輸入陣列消除作為候選的邏輯或的阿[k]和乙[K]。
- 剩下的最低候選人是結果。
def lowest_avoidable(A, B):
"""Return the lowest value avoidable in a combined sequence C
with either C[k] == A[k] or C[k] == B[k] for all k in range(len(A)). """
# C = [ A[k] | B[k] for k in range(len(A)) ] reduced to "lowest not in C"
C = [False] * (len(A) 1)
for k in range(len(A)):
combined = A[k] | B[k]
# with C padded to the next power of 2, this could be branch-free
if 0 <= combined <= len(A):
C[combined] = True
# print(C)
for k in range(1, len(C)):
if not C[k]:
return k
else:
return len(C)
if __name__ == '__main__':
for a, b in [[[1, 2, 4, 3], [1, 3, 2, 3]],
[[3, 2, 1, 6, 5], [4, 2, 1, 3, 3]],
[[1, 2], [1, 1]],
[[2, 3], [3, 2]],
[[1, 2], [1, 2]]]:
print(lowest_avoidable(a, b))
關于（不可能）使用由 N 主導的空間的線性時間解決方案的想法：
試圖僅保留一個候選者，它可能會在中途或被考慮的最后一對輸入值消除：
您必須保留有關亞軍的資訊。在時間常數對數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/388166.html