這個問題在我的面試中收到 3 個月后，我仍然無法弄清楚，而且我認識的人也沒有人能夠解決它。完整的問題是：
給定兩個已排序的整數陣列 ( Aand B) 和一個整數目標，當且僅當A[i] B[j]=target對于某些索引iand回傳真j。演算法必須是O(logn)時間，沒有任何空間限制。
我能拿出兩個解決方案：一個O(n)時間和O(n)空間，一個和O(nlogn)時間和O(1)空間中的一個。當我試圖及時解決它O(logn)時，我無法取得太大進展。我想我可以對陣列進行磁區并將其視為分而治之，但我不確定如何在給定目標整數的情況下選擇子陣列。任何幫助是極大的贊賞。
uj5u.com熱心網友回復：
在最壞的情況下，這個問題無法在比 Θ(n) 更快的時間內解決。考慮以下示例輸入：
A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
B = [10, 20, 31, 40, 50, 60, 70, 80, 90, 100]
target = 111
正確的結果是“真”，因為 80 31 = 111。從這個例子概括，我們可以想象這種形式的輸入，其中 A 包含 10 的倍數，B 包含 10 的倍數，除了可能的一個元素形式為 10k 1。在最壞的情況下，如果不檢查 B 的每個元素，就無法判斷 B 是否包含形式為 10k 1 的元素，因此即使我們知道 A 和 B 總是這種形式（一個特殊的在原始問題的情況下），演算法不能在次線性時間內給出絕對正確的答案。
所以要么是提出這個問題的面試官搞錯了，要么是溝通中丟失了一些東西，面試官給出的問題和這里說的問題不一樣。
uj5u.com熱心網友回復：
這不可能。對數字本身沒有任何保證（超出它們的順序），有必要單獨檢查所有數字，最多會導致O(n)時間復雜度。
為了證明這一點，假設您有一個演算法可以O(log n)及時相應地回傳 True/False 。讓我們選擇一個偶數T作為我們的目標，并用所有偶數填充其中一個串列0到(T-2)。另一個串列，我們最初將用所有奇數填充1到(T-1)。這樣，兩個元素（每個串列中的一個）永遠不會和我們的 value 相加T，因為奇數加偶數永遠不會是偶數。
現在，棘手的部分 - 我們將從奇數串列中隨機選擇一個數字，并將其替換為自身加一。如果我們3從 中選擇[1, 3, 5, 7, ...]，我們會將其替換4為 for [1, 4, 5, 7, ...]。現在，這個新的偶數元素將與偶數串列中的相應值相加到 make T，將答案從 更改False為True。我們假設的演算法需要能夠及時檢測到這種變化O(log n)。但是，我可以更改任何奇數值，并且它對其鄰居及其在原始串列中的位置的影響絕對為零。檢測這種變化的唯一方法是迭代奇數串列中的每個值，并確保它們仍然是奇數。
因此，您可能實作的最好結果是O(n)，因為除非您檢查每個值，否則我將能夠以這樣一種方式改變輸入，即在沒有您的演算法檢測到的情況下更改結果。
uj5u.com熱心網友回復：
如果答案是否定的，您必須至少查看所有元素一次才能確定，因此最壞的情況無疑是 O(n)。
通過合并序列 A[i] 和 target-B[LengthB-1-n] 直到找到相等的元素，可以實作簡單的 O(n) 時間、O(1) 空間演算法。
例如 (2, 3, 4, 5, 6, 8) 和 (0, 2, 8, 9) 給出 9 與 (2, 3, 4, 5, 6, 8) 和 (0, 1、7、9）。
注意：這種“扭曲”的原因是將問題轉為更經典、經過充分研究的問題。
uj5u.com熱心網友回復：
我認為這是可能的。如果您將問題視為在已排序矩陣中搜索目標值。
- 每次迭代，您都有一個
M x N矩陣m(m[i][j] = A[i] B[j])，并選擇中心值m[M/2][N/2]。 - 與
m[M/2][N/2]目標相比，你總是排除一個M/2 x N/2子矩陣。 M/2 x N/2重復搜索剩余的 3個子矩陣。
演算法復雜度為O(log(m) log(n))，log的基數為4/3，O(1)空間。
矩陣并沒有真正構建。
代碼：
#include <stdio.h>
int A[] = {10,20,30,40,50,60,70,80,90};
int B[] = {10,20,31,40,50,60,70,80,90};
int AResult, BResult;
int f(int ALeft, int ARight, int BLeft, int BRight, int target)
{
if(ALeft > ARight || BLeft > BRight) return 0;
int ACenterIndex = ALeft (ARight-ALeft)/2;
int BCenterIndex = BLeft (BRight-BLeft)/2;
int CenterValue = A[ACenterIndex] B[BCenterIndex];
if(CenterValue == target){
AResult = ACenterIndex;
BResult = BCenterIndex;
return 1;
}
if(CenterValue < target){
return f(ACenterIndex 1, ARight, BLeft, BCenterIndex, target)
|| f(ACenterIndex 1, ARight, BCenterIndex 1, BRight, target)
|| f(ALeft, ACenterIndex, BCenterIndex 1, BRight, target);
}
else{
return f(ACenterIndex, ARight, BLeft, BCenterIndex - 1, target)
|| f(ALeft, ACenterIndex - 1, BLeft, BCenterIndex - 1, target)
|| f(ALeft, ACenterIndex - 1, BCenterIndex, BRight, target);
}
}
int main()
{
int M=9,N=9,target=111;
AResult = BResult = -1;
if(f(0,M-1,0,N-1,target)){
printf("%d %d = %d\n",A[AResult],B[BResult],target);
}
else{
printf("not founed\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387608.html
標籤：算法
上一篇：計算偽代碼的時間復雜度
下一篇：確定哪些串列滿足要求的演算法