Cambie los elementos de dos secuencias, de modo que la diferencia de las sumas de elementos sea mínima.

Question

Una pregunta de la entrevista:

Dadas dos secuencias de enteros no ordenados a y b, su tamaño es n, todos los números se eligen al azar: intercambiar los elementos de a y b, tales que la suma de los elementos de a menos la suma de los elementos de b es mínimo.

Dado el ejemplo:

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

El resultado es (1 + 2 + 3) - (4 + 5 + 9) = -12.

Mi algoritmo: ordénelos y luego coloque los primeros n en a y déjelos en b. Es O (n lg n) en el tiempo y O (n) en el espacio. No sé cómo mejorarlo con un algoritmo con O (n) en el tiempo y O (1) en el espacio. O (1) significa que no necesitamos más espacio extra excepto las secciones 1 y 2.

¿Alguna idea?

Una pregunta alternativa sería: ¿Qué pasa si tenemos que minimizar el valor absoluto de las diferencias (minimizar |sum(a) - sum(b)|)?

Se prefiere un pensamiento python o C++.

Answer 1

solución Revisado:

1. Merge ambas listas x = de combinación (a, b).

2. Calcular media de x (complejidad O (n) Ver http://en.wikipedia.org/wiki/Selection_algorithm)

3. Usando estos elementos mediana de intercambio entre a y b. Es decir, encontrar un elemento en una que es menor que la mediana, encontrar uno en b que es más que mediana e intercambiarlos

complejidad final: O (n)

Minimizar diferencia absoluta es NP completo ya que es equivalente al problema de la mochila.

Answer 2

Lo que viene a la mente es el algoritmo siguiente esquema:

1. C = A v B
2. Partitially tipo #A (número de A) Elementos de C
3. Reste la suma de la última # B elementos de C de la suma de los primeros elementos de C. #A

usted debe notar, que no es necesario para ordenar todos los elementos, es suficiente para encontrar º e número de elementos A más pequeños.Su ejemplo dado:

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

a C solución ++:

#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; 
}