Categoría: Merge Sort

Combinar en el lugar dos listas vinculadas sin cambiar los enlaces de la primera lista

Posted on by Rudeus Greyrat

Dadas dos listas ordenadas enlazadas individualmente que tienen n y m elementos cada una, combínelas usando un espacio constante. Los primeros n elementos más pequeños en ambas listas deben formar parte de la primera lista y los demás elementos deben formar parte de la segunda lista. Se debe mantener el orden ordenado. No se nos … Continue reading «Combinar en el lugar dos listas vinculadas sin cambiar los enlaces de la primera lista»

Merge Sort with O(1) extra space merge and O(n lg n) time [Solo enteros sin signo]

Posted on by Rudeus Greyrat

Hemos hablado de Merge sort . Cómo modificar el algoritmo para que la fusión funcione en O(1) espacio extra y el algoritmo aún funcione en O(n Log n) tiempo. Podemos suponer que los valores de entrada son solo números enteros. Ejemplos:  Input : 5 4 3 2 1 Output : 1 2 3 4 5 … Continue reading «Merge Sort with O(1) extra space merge and O(n lg n) time [Solo enteros sin signo]»

Programa Java para ordenar la lista vinculada que ya está ordenada en valores absolutos

Posted on by Rudeus Greyrat

Dada una lista enlazada que se ordena en función de valores absolutos. Ordene la lista según los valores reales. Ejemplos:  Input: 1 -> -10 Output: -10 -> 1 Input: 1 -> -2 -> -3 -> 4 -> -5 Output: -5 -> -3 -> -2 -> 1 -> 4 Input: -5 -> -10 Output: -10 -> … Continue reading «Programa Java para ordenar la lista vinculada que ya está ordenada en valores absolutos»

Programa de Python para fusionar dos listas enlazadas ordenadas de modo que la lista fusionada esté en orden inverso

Posted on by Rudeus Greyrat

Dadas dos listas enlazadas ordenadas en orden creciente. Combínalos de tal manera que la lista de resultados esté en orden decreciente (orden inverso). Ejemplos:  Input: a: 5->10->15->40 b: 2->3->20 Output: res: 40->20->15->10->5->3->2 Input: a: NULL b: 2->3->20 Output: res: 20->3->2 Una solución simple es hacer lo siguiente. 1) Invertir la primera lista ‘a’ . 2) Invertir la … Continue reading «Programa de Python para fusionar dos listas enlazadas ordenadas de modo que la lista fusionada esté en orden inverso»

Quitar duplicados de una lista enlazada desordenada

Posted on by Rudeus Greyrat

Escriba una función removeDuplicates() que tome una lista y elimine cualquier Node duplicado de la lista. La lista no está ordenada. Por ejemplo, si la lista vinculada es 12->11->12->21->41->43->21, removeDuplicates() debería convertir la lista a 12->11->21->41->43.   MÉTODO 1 (Uso de dos bucles)  Esta es la forma sencilla en la que se utilizan dos bucles. El bucle … Continue reading «Quitar duplicados de una lista enlazada desordenada»

Combinar clasificación de árbol para estadísticas de orden de rango

Posted on by Rudeus Greyrat

Dada una array de n números, la tarea es responder a las siguientes consultas: kthSmallest(start, end, k) : Find the Kth smallest number in the range from array index ‘start’ to ‘end’. Ejemplos: Input : arr[] = {3, 2, 5, 1, 8, 9| Query 1: start = 2, end = 5, k = 2 Query … Continue reading «Combinar clasificación de árbol para estadísticas de orden de rango»

Recuento de substrings en una string binaria que contiene más 1 que 0

Posted on by Rudeus Greyrat

Dada una string binaria s , la tarea es calcular el número de tales substrings donde el conteo de 1 es estrictamente mayor que el conteo de 0 .  Ejemplos Entrada: S = “110011” Salida: 11 Explicación: Las  substrings en las que el recuento de 1 es estrictamente mayor que el recuento de 0 son … Continue reading «Recuento de substrings en una string binaria que contiene más 1 que 0»

Clasificación de combinación iterativa para lista vinculada

Posted on by Rudeus Greyrat

Dada una lista de números enteros enlazada individualmente, la tarea es clasificarla utilizando la clasificación por combinación iterativa.  Merge Sort a menudo se prefiere para ordenar una lista vinculada. Se discute aquí . Sin embargo, el método discutido anteriormente usa Stack para almacenar llamadas recursivas. Esto puede consumir mucha memoria si la lista vinculada que … Continue reading «Clasificación de combinación iterativa para lista vinculada»

Clasificación alternativa de la lista vinculada

Posted on by Rudeus Greyrat

Dada una lista enlazada que contiene n Nodes. El problema es reorganizar los Nodes de la lista de tal manera que los datos en el primer Node sean el primer mínimo, el segundo Node sea el primer máximo, el tercer Node sea el segundo mínimo, el cuarto Node sea el segundo máximo y así sucesivamente.  … Continue reading «Clasificación alternativa de la lista vinculada»

Programa C++ para ordenar la lista vinculada que ya está ordenada en valores absolutos

Posted on by Rudeus Greyrat

Dada una lista enlazada que se ordena en función de valores absolutos. Ordene la lista según los valores reales. Ejemplos:  Input: 1 -> -10 Output: -10 -> 1 Input: 1 -> -2 -> -3 -> 4 -> -5 Output: -5 -> -3 -> -2 -> 1 -> 4 Input: -5 -> -10 Output: -10 -> … Continue reading «Programa C++ para ordenar la lista vinculada que ya está ordenada en valores absolutos»