Scambia gli elementi di due sequenze, in modo tale che la differenza delle somme degli elementi sia minima.

Question

Una questione intervista:

Date due sequenze interi non ordinate a e b, la loro dimensione è n, tutti numeri sono scelti a caso: scambiare gli elementi di a e b, tali che la somma degli elementi di a meno la somma degli elementi di b è minima.

Dato l'esempio:

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

Il risultato è (1 + 2 + 3) - (4 + 5 + 9) = -12.

Il mio algoritmo: ordinali insieme, quindi inserisci il primo più piccolo n in a e lasciato in b. È O (n lg n) nel tempo e O (n) nello spazio. Non so come migliorarlo con un algoritmo con O (n) nel tempo e O (1) nello spazio. O (1) significa che non abbiamo bisogno di più spazio extra eccetto seq 1 e 2 stessi.

Qualche idea?

Una domanda alternativa sarebbe: Cosa fare se è necessario ridurre al minimo il valore assoluto delle differenze (minimizzare |sum(a) - sum(b)|)?

Un pensiero Python o C++ è preferito.

Answer 1

soluzione Revised:

1. unire le due liste x = merge (a, b).

2. Calcolare la mediana di x (complessità O (n) Vedi http://en.wikipedia.org/wiki/Selection_algorithm)

3. Utilizzando questi elementi di swap mediana tra ae b. Cioè, trova un elemento in una che è inferiore mediana, trovare uno in b che è più di mediana e scambiare

complessità finale: O (n)

Minimizzare differenza assoluta è NP completo poiché è equivalente al problema dello zaino.

Answer 2

cosa mi viene in mente è schema seguente algoritmo:

1. C = A v B
2. Partitially sorta #A (numero di A) Elementi di C
3. Sottrarre la somma degli ultimi # B elementi da C dalla somma del primo #A elementi da C.

si dovrebbe notare, che non è necessario ordinare tutti gli elementi, è sufficiente trovare l'Hotel Me Il numero di elementi più piccoli.Il vostro esempio dato:

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

una soluzione 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; 
}