查找兩個數組之間的最小差異

給定兩個排序的數組A，B，找到i，j，其中| A [i] -B [j] |是最小的。查找兩個數組之間的最小差異

2010-12-10 dharm0us

請說出你想知道的問題！ – 2010-12-10 18:45:10

給出2個作業題，你必須......至少自己試試。 – 2010-12-10 18:46:57

他想知道找到兩個不同陣列中任何兩個項目之間最小距離的最有效方法。 – sethvargo 2010-12-10 18:47:03

由於數組是排序的，所以可以用2個指針（每個數組一個）傳遞它們。如果|A[i+1] - B[j]| < |A[i] - B[j+1]|然後增加i，否則增量j。繼續，直到您到達其中一個數組的末尾。隨時跟蹤最小指標。

2010-12-10 18:48:13 marcog

此代碼的最壞情況運行時複雜度是多少？它應該是n^2，不是？ – Yashasvi 2014-01-27 05:42:44

O（nlogm）：對於A中的每個元素，使用二進制搜索方法來找到數組B中最接近的元素。 – Yashasvi 2014-01-27 05:45:54

如何自己找出這樣的答案？你用什麼方法解決它？ – 2014-11-19 22:07:38

回答