Блог

Предположим, что у нас есть 2 отсортированных массива целых чисел A и B и заданный интервал [L, M] . Если x является элементом A, а y — элементом B , наша задача — найти все пары (x, y), которые обладают следующим свойством: L<=y-x<=M. Какой алгоритм наиболее подходит для этой цели?

До сих пор я рассматривал следующее решение: грубая сила. Проверьте разницу всех возможных пар элементов с помощью двойного цикла.Сложность O(n ^ 2).

Немного отличающаяся версия предыдущего решения заключается в использовании того факта, что массивы сортируются, не проверяя элементы A , как только разница выходит за пределы интервала .Сложность все равно будет O (n ^ 2), но, надеюсь, наша программа будет работать быстрее в среднем случае.

Однако я считаю, что O (n ^ 2) не является оптимальным .Есть ли алгоритм с большей сложностью?

Вот решение.

Иметь указатель в начале каждого массива, скажем, i для массива A и j для массива B.

Вычислите разницу между B [j] и A [i].

Если она меньше L , увеличьте указатель в массиве B[], т.е. увеличьте j на 1

Если это больше M , увеличьте i , т.е. указатель на A.

Если разница между ними, то выполните следующее:

• поиск позиции элемента, значение которого B[j]-A[i]-L или ближайшего элемента, значение которого меньше, чем (B[j]-A[i])-L в массиве A. Это занимает O(logN) время. Скажем, позиция p . Увеличьте количество пар (x, y) на p-i 1

• Увеличить только указатель j

Мое решение подсчитывает только количество возможных пар (x, y) за O(NlogN) время

Для A=[1,2,3] и B=[10,12,15] и L=12 и M=14 ответ 3 .

Надеюсь, это поможет. Я оставляю это на ваше усмотрение, для реализации решения

Редактировать: Перечисление всех возможных пар (x, y) заняло бы O(N^2) наихудшее время. Мы сможем вернуть количество таких пар (x, y) за O(NlogN) время. Извините, что не разъяснил это раньше.

Правка 2: я прилагаю пример реализации предложенного мной метода ниже:

 def binsearch(a, x):

    low = 0
    high = len(a)-1
    while(low<=high):
        mid = (low high)/2
        if a[mid] == x:
            return mid
        elif a[mid]<x:
            k = mid
            low = low   mid
        else:
            high = high - mid

    return k

a = [1, 2, 3]
b = [10, 12, 15, 16]
i = 0
j = 0

lenA = len(a)
lenB = len(b)

L = 12
M = 14
count = 0 
result = []
while i<lenA and j<lenB:
    if b[j] - a[i] < L:
        j = j   1
    elif b[j] - a[i] > M:
        i = i   1
    else:
        p = binsearch(a,b[j]-L)
        count = count   p - i   1
        j = j   1

print "number of (x,y) pairs: ", count
  

Поскольку каждая комбинация может находиться в указанном диапазоне, наихудшим вариантом является O([A] [B]), что в основном равно O(n ^ 2)

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

 Create three variables: x,y,Z and s (set all to 0)
Create a boolean 'success' and set to false
Calculate Z = B[y] - A[x]
if Z < L
    increment y
if Z >= L and <= M
    if success is false
        set s = y
        set success = true
    increment y
    store x,y
if Z > M
    set y = s   //this may seem inefficient with my current example
                //but you'll see the necessity if you have a sorted list with duplicate values)
                //you can just change the A from my example to {1,1,2,2,3} to see what I mean
    set success = false
  

пример:
A = {1,2,3,4,5}
B = {3,4,5,6,7}
L = 2, M = 3

В этом примере первая пара — x,y . Второе число равно s. Третья пара — это значения A[x] и B[y]. Четвертое число — это Z, разница между A[x] и B[y]. Конечное значение равно X для не совпадения и O для совпадения

 0,0 - 0 - 1,3 = 2 O
    increment y
0,1 - 0 - 1,4 = 3 O
    increment y
0,2 - 0 - 1,5 = 4 X
    //this is the tricky part. Look closely at the changes this makes
    set y to s
    increment x
1,0 - 0 - 2,3 = 1 X
    increment y
1,1 - 0 - 2,4 = 2 O
    set s = y, set success = true
    increment y
1,2 - 1 - 2,5 = 3 O
    increment y
1,3 - 1 - 2,6 = 4 X
    set y to s
    increment x
2,1 - 1 - 3,4 = 1 X
    increment y
2,2 - 1 - 3,5 = 2 O
    set s = y, set success = true
    increment y
2,3 - 2 - 3,6 = 3 O
... and so on