Блог

Вчера мне было поручено решить эту проблему, и с тех пор я пытался найти для нее эффективное решение.
Деталь решения такова: учитывая два массива a [n], b [n], найдите пару (a [i],b [j]) так, чтобы abs (a [i] b [j]) было как можно меньше. Два массива состоят из целых элементов, не превышающих 1 миллиарда, а n здесь не более 10000.
Я знаю, что решение, состоящее из двух циклов for, здесь непрактично, поскольку размеры массивов меньше или равны 10000.
Я думаю о решении, в котором я буду сортировать эти элементы способом, который я еще не выяснил, чтобы мы могли легко определить сумму, которая имеет наименьшее абсолютное значение, поскольку мой класс изучает алгоритмы сортировки.
Можете ли вы помочь мне разобраться в этом.
PS: Извините, я не могу ввести здесь математические символы.

У меня есть Python код, который решает проблему за O(nlogn mlogm) O(m n) = O(nlogn mlogm) time, где 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

Вы можете отменить один из списков и отсортировать его вместе с другим списком. В этом новом списке вы ищете две последовательные записи с наименьшим расстоянием и такие, чтобы две записи были по одной из каждого исходного списка.

Если a[i], i=0,1,...,n первое и b[j], j=0,1,...,n второе, то min(|a[k] b[l]|)=min(|a[k]-(-b[l])|) . Таким образом, вместо минимизации суммы a[k] и b[l] для некоторых k,l мы можем минимизировать разницу между a[k] и -b[l] для некоторых k,l . Итак, мы ищем пару a[k] , -b[l] как можно ближе друг к другу. Такая пара должна быть последовательной в списке, полученном в результате сортировки a[i], -b[j] i,j=0,1,...,n в один список c[t] длины 2n .

Сортировка c — O (n log n), прохождение c — O (n), поэтому во времени выполнения преобладает сортировка.