給定兩個相同大小的數組，找到兩個數組中的幾個元素，它們與最小的絕對值進行求和

Question

昨天我接到了這個問題的任務，從那時起我就試圖找到一個有效的解決方案。
解決方案的細節是：給定兩個數組a [n]，b [n]，找到一個對（a [i]，b [j]），以便abs（a [i] + b [j]）儘可能小。這兩個數組由整數元素組成，不超過10億，這裏n至多爲10000.
我知道一個由兩個for循環組成的解決方案是不實用的，因爲數組的大小小於或等於10000.
I我正在考慮一種解決方案，我將以某種方式對這些元素進行排序，這是我尚未發現的，因此我們可以很容易地找出絕對值最小的和，因爲我的課正在學習排序算法。
你能幫我弄清楚這裏的方式嗎？
PS：對不起，我無法在這裏輸入數學符號。

Answer 1

我有一個Python代碼，在O(nlogn + mlogm) + O(m+n) = O(nlogn + mlogm)時間，其中n是第一陣列的長度和m是所述第二陣列的長度解決該問題。下面是代碼：

arr1.sort() 
arr2.sort(reverse = True) 
n = len(arr1) 
m = len(arr2) 
print arr1 
print arr2 
minim = abs(arr1[0] + arr2[0]) 

i = 0 
j = 0 

while i<n and j<m: 
    minimum = abs(arr1[i] + arr2[j]) 
    minim = min(minim,minimum) 
    if arr1[i]>0 and arr2[j]>0: 
     j += 1 
    elif arr1[i]<=0 and arr2[j]<=0: 
     i += 1 
    elif arr1[i]>0 and arr2[j]<=0: 
     if abs(arr1[i]) > abs(arr2[j]): 
      j += 1 
     else: 
      i += 1 
    elif arr1[i]<=0 and arr2[j]>0: 
     if abs(arr1[i]) > abs(arr2[j]): 
      i += 1 
     else: 
      j += 1 

print minim 

實施例：

arr1[] = [-23, -10, 30, 44, 45]

arr2[] = [61, 55, 32, 22, -55]

答案：1

Answer 2

您可以否定其中一個列表並將其與其他列表一起排序。在這個新的列表中，您可以查找兩個連續的最小距離的條目，並且這兩個條目是每個原始列表中的一個條目。

如果a[i], i=0,1,...,n是第一個，而b[j], j=0,1,...,n是第二個，那麼min(|a[k]+b[l]|)=min(|a[k]-(-b[l])|)。因此，對於某些k,l，我們可以將a[k]和b[l]的總和最小化，而對於某些k,l，我們可以最小化a[k]和-b[l]之間的差異。所以我們尋找一對a[k],-b[l]儘可能接近。這樣的一對必須在從對i,j=0,1,...,n進行排序a[i], -b[j]獲得的列表中連續成爲長度爲2n的單個列表c[t]。

排序c是O（n日誌n），運行通過c是O（n），所以運行時間是由排序占主導地位。