Блог

Я изо всех сил пытаюсь найти эффективный алгоритм для выполнения следующей задачи:

Учитывая два массива A и B одинаковой длины, разница между двумя массивами определяется как:

 diff = |a[0]-b[0]|   |a[1]-b[1]|  ... |a[a.length-1]-b[b.length-1]|
 

Я должен найти минимально возможную разницу между A и B, и мне разрешено заменить не более одного элемента из A любым другим элементом в A. Обратите внимание, что от вас не требуется выполнять замену.

Например:

 A = [1,3,5]
B = [5,3,1]
 

Если мы заменим A[2] на A[0], то разница между двумя массивами будет равна:

 |1-5|   |3-3|   |1-1| = 4
 

Это минимально возможная разница между двумя массивами. Никакая другая замена элемента в A другим элементом в A не приведет к меньшей разнице между A и B.

Как бы я решил эту проблему? Я знаю, как решить проблему в O (n ^ 2) (грубая сила), но изо всех сил пытаюсь найти более эффективный способ.

Спасибо!

Я реализую предложение Шридхара по определению наилучшей модификации для каждого элемента в отдельности за O (n log n) время и выбираю лучшую.

 import bisect


def abs_diff(x, y):
    return abs(x - y)


def find_nearest(sorted_a, y):
    i = bisect.bisect(sorted_a, y)
    return min(
        sorted_a[max(i - 1, 0) : min(i   1, len(sorted_a))],
        key=lambda z: abs_diff(z, y),
    )


def improvement(x, y, z):
    return abs_diff(x, y) - abs_diff(z, y)


def min_diff(a, b):
    sorted_a = sorted(a)
    nearest = [find_nearest(sorted_a, y) for y in b]
    return sum(map(abs_diff, a, b)) - max(map(improvement, a, b, nearest))


print(min_diff([1, 3, 5], [5, 3, 1]))
 

Этот пост ошибочно отвечает на вариант вопроса, который заключается в том, чтобы разрешить один обмен двумя элементами в A. Я думал, что оставлю это, так как я работал над этим.

Ниже приведены общие возможности для улучшения. Мы можем видеть, что улучшение происходит, когда пара, с которой мы меняемся местами, имеет противоположный порядок (например, if a1 < b1 then a2 > b2 и наоборот). Присмотревшись повнимательнее, мы видим, что следующее качество заключается в том, что лучший кандидат на обмен имеет наибольшее совпадение с первой парой.

Мы можем создать O(n log n) процедуру, сначала отсортировав все заданные пары по их нижнему элементу, а затем обработав их в порядке убывания нижнего элемента. По мере спуска сохраняйте одно дерево статистики порядка для пар where a < b и другое для пар where b ≤ a . Упорядочите деревья по старшему элементу каждой пары и сохраните два украшения: (1) наибольший интервал, видимый в левом поддереве, и (2) наименьший нижний элемент, видимый в левом поддереве.

Для каждого обработанного элемента выберите большее перекрытие между (1) парой в противоположном дереве с равным или меньшим старшим элементом и наибольшим интервалом (соответствующим первому украшению дерева) и (2) парой в противоположном дереве с более высоким или равным старшим элементом и наименьшимнижний элемент (соответствующий второму украшению дерева).

(Поскольку мы обрабатываем пары в порядке убывания low , видимые low s всегда будут равны или выше текущего элемента.)

(1)

 Original:
     a1-----------b1
                     a2----b2
Total: ----------- ----

Swapped:
     a1--------------------b2
                  b1-a2
Total: -------------------- -

Result: worse.
 

(2)

 Original:
     a1-----------b1
                     b2----a2
Total: ----------- ----

Swapped:
     a1--------------b2
                  b1-------a2
Total: -------------- -------

Result: worse.
 

(3)

 Original:
     a1-----------b1
             a2------b2
Total: ----------- ------

Swapped:
     a1--------------b2
             a2---b1
Total: -------------- ---

Result: the same.
 

(4)

 Original:
     a1-----------b1
             b2------a2
Total: ----------- ------

Swapped:
     a1------b2
                  b1-a2
Total: ------ -

Result: BETTER.
Improvement: 2 * dist(b2, b1)
 

(5)

 Original:
     a1--------------b1
           a2----b2
Total: -------------- ----

Swapped:
     a1----------b2
           a2--------b1
Total: ---------- --------

Result: the same.
 

(6)

 Original:
     a1--------------b1
           b2----a2
Total: -------------- ----

Swapped:
     a1----b2
                 a2--b1
Total: ---- --

Result: BETTER.
Improvement: 2 * dist(b2, a2)
 

(7)

 Original:
     a1--------------b1
 b2--------a2
Total: -------------- --------

Swapped:
 b2----a1
           a2--------b1
Total: ---- --------

Result: BETTER.
Improvement: 2 * dist(a1, a2)
 

(8)

 Original:
     a1-----------b1
 b2-------------------a2
Total: ----------- -------------------

Swapped:
 b2--a1
                  b1--a2
Total: -- --

Result: BETTER.
Improvement: 2 * dist(a1, b1)