Поменяйте местами элементы двух последовательностей так, чтобы разница сумм элементов была минимальной.

Question

Вопрос для интервью:

Учитывая две неупорядоченные целочисленные последовательности a и b, их размер равен n, все числа выбираются случайным образом: меняются элементы a иb, так что сумма элементов a минус сумма элементов b минимальна.

Приведенный пример:

a = [ 5 1 3 ]
b = [ 2 4 9 ]

Результат (1 + 2 + 3) - (4 + 5 + 9) = -12.

Мой алгоритм: отсортируйте их вместе, а затем поместите первые наименьшие n целые числа в a и оставьтев b.Это O (n lg n) во времени и O (n) в пространстве.Я не знаю, как улучшить его до алгоритма с O (n) во времени и O (1) в пространстве.O (1) означает, что нам не нужно больше дополнительного пространства, кроме самих seq 1 и 2.

Есть идеи?

Альтернативный вопрос: а если нам нужно минимизировать абсолютную величину различий (минимизировать |sum(a) - sum(b)|)?

Предпочтение отдается питонскому или C ++-мышлению.

Answer 1

Пересмотренное решение:

1. Объединить оба списка x = объединить (a, b).

2. Рассчитать медиану x (сложность O (n) См. http://en.wikipedia.org/wiki/Selection_algorithm)

3. При использовании этой медианы меняются элементы между a и b.То есть, найти элемент в a, который меньше медианы, найти элемент в b, который больше медианы, и поменять их местами

Конечная сложность: O (n)

Сведение к минимуму абсолютной разности является завершением NP, поскольку оно эквивалентно проблеме ранца.

Answer 2

Мне приходит в голову следующий алгоритм:

1. C = A v B
2. Частичная сортировка #A (число A) Элементы C
3. Вычтите сумму последних #B элементов из C из суммы первых #A элементов из C.

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

1. C = {5, 1, 3, 2, 4, 9}
2. C = {1, 2, 3, 5, 4, 9}
3. (1 + 2 + 3) - (5 + 4 + 9) = -12

Решение C ++:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    // Initialize 'a' and 'b'
    int ai[] = { 5, 1, 3 };
    int bi[] = { 2, 4, 9 };
    std::vector<int> a(ai, ai + 3);
    std::vector<int> b(bi, bi + 3);

    // 'c' = 'a' merged with 'b'
    std::vector<int> c;
    c.insert(c.end(), a.begin(), a.end());
    c.insert(c.end(), b.begin(), b.end());

    // partitially sort #a elements of 'c'
    std::partial_sort(c.begin(), c.begin() + a.size(), c.end());

    // build the difference
    int result = 0;
    for (auto cit = c.begin(); cit != c.end(); ++cit)
        result += (cit < c.begin() + a.size()) ? (*cit) : -(*cit);

    // print result (and it's -12)
    std::cout << result << std::endl;
}