dividir una lista enlazada en 2 listas pares que contienen los números más pequeños

Dada una lista enlazada de enteros en orden aleatorio, divídala en dos nuevas listas enlazadas de modo que la diferencia en la suma de elementos de cada lista sea máxima y la la longitud de las listas difiere en no más de 1 (en el caso de que la lista original tenga un número impar de elementos). No puedo suponer que los números en la lista sean únicos.dividir una lista enlazada en 2 listas pares que contienen los números más pequeños

El algoritmo que pensé fue hacer una especie de mezcla en la lista enlazada originales (O (N & middot; log n) tiempo, O (n) espacio) y luego usar una función recursiva para caminar hasta al final de la lista para determinar su longitud, haciendo la división mientras la función recursiva se está desenrollando. La función recursiva es O (n) tiempo y O (n) espacio.

¿Es esta la solución óptima? Puedo publicar mi código si alguien piensa que es relevante.

Fuente

2011-02-09 Robert S. Barnes

Si tu La implementación de la lista vinculada mantiene una propiedad de tamaño, luego solo tiene que caminar hasta la mitad de la lista para cortarla por la mitad. (Puede que quiera visitar http://codereview.stackexchange.com!) – Jeremy

@Jeremy Heiler: Propiedad sin tamaño, solo una lista muy simple de enlaces jane, realmente nada más que un grupo de nodos unidos entre sí. –

A menos que su examen requiera que implemente el ordenamiento, también puede usar Collections.sort para hacer la ordenación. – karakuricoder

No, no es óptimo; puede encontrar el median of a list in O(n), luego ponga la mitad de ellos en una lista (menor que la mediana o igual, hasta el tamaño de la lista sea n/2) y la mitad de ellos en otra lista ((n + 1)/2). Su diferencia suma se maximiza, y no hay necesidad de clasificar (O (N & middot;. Log (n)) Todas las cosas se harán en O (n) (espacio y tiempo)

Fuente

2011-02-09 13:23:21

El enlace que proporcionó parece indicar que este algoritmo es adecuado para matrices de acceso aleatorio. ¿Estás seguro de que esto funciona para las listas enlazadas? –

@Robert S. Barnes: Si es necesario, podríamos copiar la lista primero en una matriz y luego volver, todavía O (n). –

Una cosa más, en base a este análisis http://www.soe.ucsc.edu/classes/cmps102/Spring05/selectAnalysis.pdf del algoritmo Median of Medians, requiere que los elementos en la matriz sean únicos. No puedo suponer eso. –

¿Por qué lo hacen. necesita una función recursiva. Mientras clasifica la lista, puede contar los elementos. Luego simplemente divídala por la mitad. Esto deja O (n) espacio requerido

Incluso si no puede contar la longitud de la lista mientras ordena, aún puede dividir en O (n) tiempo y O (1) espacio: obtener dos iteradores de lista al principio, avanzar los primeros 2 elementos en cada paso, segundo 1 elemento en cada paso. Cuando llega por primera vez a la lista final - cortar en el segundo

Fuente

2011-02-09 13:24:32 blaze

I ya estoy dividiéndome en O (n) tiempo. Toma O (n) espacio porque estoy haciendo copias de la LL original. –

dividir una lista enlazada en 2 listas pares que contienen los números más pequeños

Respuesta

Cuestiones relacionadas