Introducci贸n

1

Arrays y Strings para resolver algoritmos avanzados

2

Arrays y Strings en detalle

Dos Apuntadores

3

Patr贸n de Dos Apuntadores

4

Verifying Alien Dictionary: an谩lisis del problema

5

Soluci贸n de Verifying Alien Dictionary

6

Playground: Verifying Alien Dictionary

7

Programando Verifying Alien Dictionary con JavaScript

8

Merge Two Sorted Lists: an谩lisis del problema

9

Soluci贸n de Merge Two Sorted Lists

10

Playground: Merge Two Sorted Lists

11

Programando Merge Two Sorted Lists con Python

12

Container With Most Water: an谩lisis del problema

13

Soluci贸n de Container With Most Water

14

Playground: Container with Most Water

15

Programando Container With Most Water con Java

16

Reto: Trapping Rain Water

17

Ejercicios recomendados de Dos Apuntadores

18

Ejercicios resueltos de Dos Apuntadores

Ventana Deslizante

19

Patr贸n de Ventana Deslizante

20

Longest Substring Without Repeating Characters: an谩lisis del problema

21

Soluci贸n de Longest Substring Without Repeating Characters

22

Playground: Longest Substring Without Repeating Characters

23

Programando Longest Substring Without Repeating Characters con Python

24

Ejercicios recomendados de Ventana Deslizante

25

Ejercicios resueltos de Ventana Deslizante

B煤squeda Binaria

26

Algoritmo de B煤squeda Binaria

27

Search in Rotated Arrays: an谩lisis del problema

28

Soluci贸n de Search in Rotated Arrays

29

Playground: Search in Rotated Arrays

30

Programando Search in Rotated Arrays

31

Search 2D Array Matrix: an谩lisis del problema

32

Soluci贸n de Search 2D Array Matrix

33

Playground: Search 2D Array Matrix

34

Programando Search 2D Array Matrix

Pr贸ximos pasos

35

Toma el Curso Avanzado de Algoritmos: Estructuras de Datos Lineales

No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Soluci贸n de Merge Two Sorted Lists

9/35
Recursos

Aportes 23

Preguntas 1

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

Para usar la longitud adecuada solo intercambi茅 los valores en caso necesario, y para poder tener 0s le asign茅 valor nulo a los indices extra del primer arreglo

Incluyo caso de prueba que considera estos dos casos

def mergeLists(list1, list2, m, n):
    if m > n:
        n,m = m,n
        list1,list2 = list2,list1
    p1 = m-1
    p2 = n-1
    for mp in range(m+n-1, -1, -1):
        if p1 < 0 or list2[p2] > list1[p1] or list1[p1] == None:
            list1[mp] = list2[p2]
            p2 -= 1
        else:
            list1[mp] = list1[p1]
            p1 -= 1
    return list1
    
list2 = [0,2,3,None,None,None,None]
n = 3
list1 = [-4,2,3,9]
m = 4
print(mergeLists(list1, list2,m,n))

En js

const mergeTwoSortedLists = (nums1, nums2, m, n) => {
    const lastIndex = m + n - 1;
    const n1Copy = [...nums1]
    let n1Pointer = m - 1;
    let n2Pointer = n - 1;
    for (let i = lastIndex; i >= 0; i--) {
        const n1Higher = n1Copy[n1Pointer] ?? Number.MIN_SAFE_INTEGER;
        const n2Higher = nums2[n2Pointer] ?? Number.MIN_SAFE_INTEGER;
        
        if (n1Higher > n2Higher) {
            n1Copy[i] = n1Higher
            n1Pointer--
        } else {
            n1Copy[i] = n2Higher
            n2Pointer--
        }
    }
    return n1Copy;
}

Mi soluci贸n en Python. Es m谩s general y es indiferente a los tama帽os de ambas listas. Quise hacerla lo m谩s sencilla posible, sin hacer desplazamientos o asignaciones con slicing. Creo que resulta en complejidad O(n log(n)). ```js def ordenamiento_de_listas(nums1, nums2): m = len(nums1) n = len(nums2) for i in range(n): nums1.append(0) idx2 = m # Apuntador hacia las ubicaciones a llenar idx1 = 0 # Apuntador a la posici贸n donde hay que cambiar el n煤mero # El desplazamiento de los n煤meros ocurre entre idx1 e idx2 for j in range(n): num = nums2[j] # Hallar idx1 for i in range(idx2): a = nums1[i] b = nums1[i+1] if num<=a and num<b: # n<=a<b idx1 = i break elif num>a and num<=b: # a
``` function mergeList(nums1,nums2){聽 聽 *let* n = nums2.length, m;聽 聽 聽 nums2.forEach(element => {聽 聽 聽 聽 nums1.push(0);聽 聽 });聽 聽 m = nums1.length-n; 聽 聽 for(*let* i = 0; i\
`function mergeList(nums1,nums2){聽 聽 ``let`` n = nums2.length, m;聽 聽 聽 nums2.forEach(element => {聽 聽 聽 聽 nums1.push(0);聽 聽 });聽 聽 m = nums1.length-n;` `聽 聽 for(``let`` i = 0; i
hpta que soluci贸n mas linda la de la profe jjj, yo hice la m铆a pero no estan eficiente porque recorre los arreglos muchas veces. ```js const nums1 = [1, 2, 3, 0, 0, 0, 0]; const m = 3; const nums2 = [-4, 2, 3, 9]; const n = 4; const min_value = (nums1, nums2) => { if (nums1[0] < nums2[0]) { return nums1[0]; } else { return nums2[0]; } }; const max_value = (nums1, nums2) => { max_leng_value1 = nums1.length - nums2.length - 1; max_leng_value2 = nums2.length - 1; if (nums1[max_leng_value1] > nums2[max_leng_value2]) { return nums1[max_leng_value1]; } else { return nums2[max_leng_value2]; } }; function addMerge(array, value, merge) { for (let i = 0; i < array.length; i++) { if (array[i] === value && value != 0) { merge.push(value); } } return merge; } function mergeTwoSorted(nums1, nums2) { const min = min_value(nums1, nums2); const max = max_value(nums1, nums2); let array_merged = []; for (let value = min; value <= max; value++) { addMerge(nums1, value, array_merged); addMerge(nums2, value, array_merged); } return array_merged; } console.log(mergeTwoSorted(nums1, nums2)); ```
esta fue mi soluci贸n en java, olvid茅 lo de los numeros m y n xd pero tambien funciona ```js public class MergeTwoSortedLists { public static void main(String[] args) { int[] list1 = {1,2,3,4,7,9}; int[] list2 = {2,5,6,8,10,11,12}; int[] mergedList = mergeTwoSortedLists(list1, list2); for (int j : mergedList) { System.out.println(j); } } private static int[] mergeTwoSortedLists(int[] list1, int[] list2) { int[] mergedList = new int[list1.length + list2.length]; int index1 = 0; int index2 = 0; for(int i = 0; i < mergedList.length; i++) { int insertValue; if(index1 == list1.length) { insertValue = list2[index2]; index2++; mergedList[i] = insertValue; continue; } if(index2 == list2.length) { insertValue = list1[index1]; index1++; mergedList[i] = insertValue; continue; } if(list1[index1] <= list2[index2]){ insertValue = list1[index1]; index1++; } else { insertValue = list2[index2]; index2++; } mergedList[i] = insertValue; } return mergedList; } } ```
comparto mi solucion en c# ```js public List<int> MergeTwoList(List<int> list1, List<int> list2, int m, int n) { List<int> result = new List<int>(); int pointerList2 = 0; int pinterList1 = 0; for (int i = 0; i < m; i++) { if (isNullSearchIndexInList(list2, pointerList2)) { result.Add(list1[pinterList1]); pinterList1++; } else if (isNullSearchIndexInList(list1, pinterList1)) { result.Add(list2[pointerList2]); pointerList2++; } else { if (list1[pinterList1] <= list2[pointerList2]) { result.Add(list1[pinterList1]); pinterList1++; } else { result.Add(list2[pointerList2]); pointerList2++; } } } return result; } public bool isNullSearchIndexInList(List<int> List, int indexSearch) { if (List.Count>=indexSearch) { return true; } return false; } ```public List\<int> MergeTwoList(List\<int> list1, List\<int> list2, int m, int n) { List\<int> result = new List\<int>(); int pointerList2 = 0; int pinterList1 = 0; for (int i = 0; i < m; i++) { if (isNullSearchIndexInList(list2, pointerList2)) { result.Add(list1\[pinterList1]); pinterList1++; } else if (isNullSearchIndexInList(list1, pinterList1)) { result.Add(list2\[pointerList2]); pointerList2++; } else { if (list1\[pinterList1] <= list2\[pointerList2]) { result.Add(list1\[pinterList1]); pinterList1++; } else { result.Add(list2\[pointerList2]); pointerList2++; } } } return result; } public bool isNullSearchIndexInList(List\<int> List, int indexSearch) { if (List.Count>=indexSearch) { return true; } return false; }

Yo llegue a este O(n+m) tambien pero si utilice un array aux:

export const mergedTwoSortedLists = (nums1: number[], nums2: number[], m: number, n: number): number[] | false => {
  const joinArray: number[] = [];
  let i = 0; // index for nums1
  let j = 0; // index for nums2

  // Validations
  if (nums1.length !== (m + n)) return false;
  if (nums2.length !== n) return false;
  if (nums1.slice(n).every(num => num === 0) === false) return false;

  while (true) {
    // This means we don't have more numbers to check, so push all
    // the rest of numbers of nums2 to joinArray.
    if (nums1[i] === 0) {
      joinArray.push(...nums2.slice(j));
      break;
    }

    // nums1[i] is less than nums2 of current index,
    // push nums1[i] to join array.
    if (nums1[i] > nums2[j] === false) {
      joinArray.push(nums1[i]);
      i = i + 1;
    } else { // nums2 of current index is less than 
      joinArray.push(nums2[j]);
      j = j + 1;
    }
  }

  return joinArray;
};
yo utilice una variable vacia para crear un nuevo array filtrando el orden y los elementos a ser pusheados no se si eso se permitia `function mergeTwoSortedList (list_1, size_1, list_2, size_2){` ` const longestList = Math.max(list_1.length, list_2.length)` ` let newSortedList = []` ` for(let i = 0; i <= longestList - 1; i++){` ` if(list_1[i] !== 0 && list_2[i] !== 0){` ` if(list_1[i] > list_2[i]){` ` newSortedList.push( list_2[i], list_1[i])` ` }else{` ` newSortedList.push( list_1[i], list_2[i])` ` }` ` } ` ` }` ` return newSortedList` `}`

No es como en el video pero funciona jaja

package merge_2_sorted_arrays_problem;
import java.util.Arrays;

public class MergeSortArrays {

    public static int[] mergeArrays (int[] nums1, int[] nums2, int m){

        int[] mergeNums;
        mergeNums = nums1;
        int nums2Index = 0;

        for (int index = m; index < nums1.length; index++){

            mergeNums[index] = nums2[nums2Index];
            nums2Index++;
        }

        Arrays.sort(mergeNums);

        return mergeNums;
    }
}

les comparto mi solucion

function MergeTwoSortedLists(list1, list2) {
    let counter1 = 0
    let counter2 = 0
    const result = []
    const list3 = list1.slice(0, list1.findIndex(element => element === 0))
    for (let index = 0; index < list1.length; index++) {
        if (list3[counter1] < list2[counter2]) {
            result.push(list3[counter1])
            counter1++
        }
        else {
            result.push(list2[counter2])
            counter2++
        }
    }
    return result
}
var nums1 = [1, 2, 3, 4, 11,12,20,0, 0, 0, 0, 0,0];
var m = 7;
var nums2 = [2, 5, 6,6,8,8];
var n = 6;
var i = 0, j = 0;
var result = [];

while (i < m - 1 || j < n - 1) {
    if (nums1[i] <= nums2[j]) {
        result.push(nums1[i]);
        i++;
    } else {
        result.push(nums2[j]);
        j++;
    }

    if (i == m) { //NUMS1 has finished
        sort("nums2", j);
        j = n-1;
    } else if (j == n) {
        sort("nums1", i);
        i = m-1;
    }
}

function sort(nums, iterator) {
    var numbers;
    switch (nums) {
        case "nums1":
            numbers = nums1;
            var fin = m;
            break;
        case "nums2":
            numbers = nums2;
            var fin = n;
            break;
    }
    for (let k = iterator; k < fin; k++) {
        result.push(numbers[k]);  // THE NUMBERS ARE SORTED
    }
}

console.log(result);
return result;

Hize este approach con metodos de JS :

const mergeTwoLists = (array1, array2) =>
  array1
    .concat(array2)
    .filter((number) => number !== 0)
    .sort();
  • no hab铆a entendido para que era el m y el n, segu铆a pensando en hacerlo similar al del alien, pero que locura como lo que se ve铆a complejo se ve mas sencillo.

Mi soluci贸n en Java 馃槂

public static List<Integer> MergeTwoSortedList(List<Integer> nums1, List<Integer> nums2) {
        nums1 = nums1.subList(0, nums1.size() - nums2.size());
        List<Integer> nums = new ArrayList<Integer>();

        int i = 0;
        int j = 0;

        while (true) {
            System.out.println(nums);
            if (i >= nums1.size()) { // Verifica si se alcanzaron los l铆mites del primer array
                nums2 = nums2.subList(j, nums2.size()); // Concatena los valores que sobraron del segundo array
                nums.addAll(nums2);
                break;
            } else {
                if (j >= nums2.size()) { // Verifica si se alcanzaron los l铆mites del segundo array
                    nums1 = nums1.subList(i, nums1.size()); // Concatena los valores que sobraron
                    nums.addAll(nums1);
                    break;
                } else {
                    // Obtiene los valores de los arrays. Se compara nums2 contra nums1.
                    if (nums2.get(j) == nums1.get(i)) { // Si son iguales, los a帽ade directo al nuevo array.
                        nums.add(nums1.get(i));
                        nums.add(nums2.get(j));

                        i++;
                        j++;
                    } else {
                        if (nums2.get(j) > nums1.get(i)) { // Si el de nums2 es mayor que el de nums1...
                            nums.add(nums1.get(i)); // Se a帽ade el de nums1 al array final.
                            i++; // Pasa al siguiente valor de nums1
                        } else { // Si el de nums2 es menor que el de nums1...
                            nums.add(nums2.get(j)); // Se a帽ade el de nums2 al array final.
                            // nums2_copy.remove(j);
                            j++; // Pasa al siguiente valor de nums2
                        }
                    }

                }
            }
        }

        return nums;
    }

Mi soluci贸n en Java:

package tests;

import java.util.Arrays;

/**
 *
 * @author juanr
 */
public class MergeTwoSortedLists {

    public static void mergeTwoSortedLists(int[] nums1, int[] nums2, int m, int n) {
        int ap1 = m - 1;
        int ap2 = n - 1;
        int ap3 = nums1.length - 1;

        if (nums1[ap1] < nums2[0]) {
            System.arraycopy(nums2, 0, nums1, m, n);
        } else if (nums2[ap2] < nums1[0]) {
            System.arraycopy(nums1, 0, nums1, n, m);
            System.arraycopy(nums2, 0, nums1, 0, n);
        } else {
            while (ap3 >= 0) {
                if (ap1 > 0) {
                    if (nums1[ap1 - 1] < nums1[ap1] && nums1[ap1 - 1] > nums2[ap2]) {
                        nums1[ap3] = nums1[ap1];
                        ap3--;
                        ap1--;
                        nums1[ap3] = nums1[ap1];
                        ap3--;
                        ap1--;
                    }
                }

                if (ap3 == 0 && (ap1 < 0 || ap2 < 0) && nums1[1] < nums1[0]) {
                    int aux = nums1[0];
                    nums1[0] = nums1[1];
                    nums1[1] = aux;
                } else if (nums2[ap2] > nums1[ap1]) {
                    nums1[ap3] = nums2[ap2];
                    ap2--;
                    ap3--;
                } else if (nums2[ap2] == nums1[ap1]) {
                    nums1[ap3] = nums2[ap2];
                    ap3--;
                    ap1--;
                } else if (nums2[ap2] < nums1[ap1]) {
                    nums1[ap3] = nums1[ap1];
                    ap3--;
                    nums1[ap3] = nums2[ap2];
                    ap3--;
                    ap2--;
                    ap1--;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 0, 0, 0, 0};
        int[] nums2 = {-4, 2, 3, 9};
        int m = 3;
        int n = nums2.length;

        mergeTwoSortedLists(nums1, nums2, m, n);

        System.out.println(Arrays.toString(nums1));

        nums1 = new int[]{1, 2, 10, 0, 0, 0, 0};
        nums2 = new int[]{-4, 2, 3, 9};
        m = 3;
        n = nums2.length;

        mergeTwoSortedLists(nums1, nums2, m, n);

        System.out.println(Arrays.toString(nums1));

        nums1 = new int[]{1, 17, 18, 0, 0, 0, 0};
        nums2 = new int[]{-4, 2, 3, 9};
        m = 3;
        n = nums2.length;

        mergeTwoSortedLists(nums1, nums2, m, n);

        System.out.println(Arrays.toString(nums1));

        nums1 = new int[]{-4, 2, 3, 0, 0, 0, 0};
        nums2 = new int[]{10, 17, 18, 19};
        m = 3;
        n = nums2.length;

        mergeTwoSortedLists(nums1, nums2, m, n);

        System.out.println(Arrays.toString(nums1));

        nums1 = new int[]{10, 17, 18, 0, 0, 0, 0};
        nums2 = new int[]{-4, 2, 3, 9};
        m = 3;
        n = nums2.length;

        mergeTwoSortedLists(nums1, nums2, m, n);

        System.out.println(Arrays.toString(nums1));
    }
}

Comparto mi posible soluci贸n

    /*
        Dadas dos listas de n煤meros enteros nums1 y
        nums2, cada una ordenada en orden ascendente, y
        dos enteros m y n, que representan la cantidad de
        elementos en nums1 y nums2 respectivamente.
        Combinar nums1 y nums2 en un 煤nico array ordenado
        de forma ascendente.
        Para ello, nums1 tiene una longitud de m + n, donde
        los primeros m elementos denotan los elementos que
        deben ser combinados, y los 煤ltimos n elementos son
        0 y deben ser ignorados.

        Entrada de Datos:
            nums1 = [1,2,3,0,0,0]
            m = 3

            nums2 = [2,5,6]
            n = 3

        Salida Esperada:
            [1,2,2,3,5,6]

        resultado = [1,2,3,0,0,0] + [2,5,6] = [1,2,3,2,5,6]

        //  ORDERNAR DE MENOR AL MAS ARRIBA
        r = [1,2,3,2,5,6]

        i = 4;
        next = i + 1 = 5;

        r[i](5) < r[next](6); 
        r[i](3) < r[next](2) i++ ;
        rr = [1,2,2,3,5,6]
    */

    public static int[] MergeTwoSortedList(int[] nums1, int m, int[] nums2, int n)
    {
        var newListOutput = new int[m + n];
        var mergedList = MergeLists(nums1, nums2, m, n);
        return ReorderList(mergedList);
    }

    private static int[] ReorderList(int[] mergedList)
    {
        var newList = new int[mergedList.Length];

        for (int i = 0; i < newList.Length - 1; i++)
        {
            if (mergedList[i] == 0) continue;

            if (mergedList[i] < mergedList[i + 1])
            {
                newList[i] = mergedList[i];
                newList[i + 1] = mergedList[i + 1];
            }
            else
            {
                newList[i] = mergedList[i + 1];
                newList[i + 1] = mergedList[i];
                i++;
            }
        }

        return newList;
    }

    private static int[] MergeLists(int[] nums1, int[] nums2, int m, int n)
    {
        var result = new int[m + n];
        int filledSpacesCount = 0;

        for (int i = 0; i < nums1.Length; i++)
        {
            if (nums1[i] == 0) continue;
            result[filledSpacesCount++] = nums1[i];
        }

        for (int i = 0; i < nums2.Length; i++)
        {
            if (nums2[i] == 0) continue;
            result[filledSpacesCount++] = nums2[i];
        }

        return result;
    }

En ruby y con recursi贸n:

def entry_point(l1, n, l2, m)
  l1.pop(m)
  selection_sort(l1 + l2)
end

def selection_sort(arr)
  if arr.length <= 1
    return arr
  else
    min_idx = arr.index(arr.min)
    rest = arr[0...min_idx] + arr[min_idx+1..-1]
    return [arr[min_idx]] + selection_sort(rest)
  end
end

p entry_point([1, 2, 3, 0, 0, 0, 0], 3, [-4, 2, 3, 9], 4)

Esta es la solucion al problema para dos arreglos:

 class Solution {
    public int[] mergeTwoLists(int[] list1, int m, int[] list2, int n) {
        int first = m - 1;
        int second = n - 1;
        int sortedIdx = list1.length - 1;
        while (first >= 0 && second >= 0) {
            if (list1[first] >= list2[second]) {
                list1[sortedIdx] = list1[first];
                sortedIdx--;
                first--;
            } else {
                list1[sortedIdx] = list2[second];
                sortedIdx--;
                second--;
            }
        }
        while (first >= 0) {
            list1[sortedIdx] = list1[first];
            sortedIdx--;
            first--;
        }
        while (second >= 0) {
            list1[sortedIdx] = list2[second];
            sortedIdx--;
            second--;
        }
        return list1;
    }
}

Esta es la version de LeetCode donde se manejan LinkedLists:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode sentinel = new ListNode(-1);
        ListNode tail = sentinel;
        ListNode first = list1;
        ListNode second = list2;
        while (first != null && second != null) {
            if (first.val <= second.val) {
                tail.next = first;
                first = first.next;
            } else {
                tail.next = second;
                second = second.next;
            }
            tail = tail.next;
            tail.next = null;
        }
        tail.next = first != null ? first : second;
        return sentinel.next;
    }
}

La complejidad de tiempo de ambas soluciones es:
T = O(n + m), donde:
n = Es el numero de elementos en la primera lista
m = Es el numero de elementos en la segunda lista

S = O(1)

Comparto mis soluciones:

== Sin Inmutabilidad (Creando un nuevo ARRAY) ==

function mergeTwoSortedLists(list1: Array<number>, list2: Array<number>) : Array<number> {
    return  [...list1, ...list2].filter((num) => num > 0).sort((a, b) => a - b);
}

== Con Inmutabilidad (Utilizando el ARRAY m谩s largo de los enviados en los argumentos de la funcci贸n) ==

function mergeTwoSortedLists(list1: Array<number>, list2: Array<number>) : Array<number> {
    let counter = 0;
    let longerList;
    let shorterList;
    if (list1.length > list2.length) {
        longerList = list1;
        shorterList = list2;
    } else {
        longerList = list2;
        shorterList = list1;
    }
    for (let index = longerList.length; index > shorterList.length; index--) {
        longerList[index - 1] = shorterList[counter];
        counter++;
    }
    return longerList.sort((a, b) => a - b);
}

esta es la segunda despues del minuto 7 鈥
+

?

function ordenarCrudo(nums1,nums2,n,m){
    while( m>0 || n>0){
      if(nums1[m-1]>nums2[n-1])  {
        nums1[m+n-1]=nums1[m-1];
        m--;
      }else if(nums1[m-1]<nums2[n-1]){
        nums1[m+n-1]=nums2[n-1];
        n--;
      }else if( n==0){
        nums1[m+n-1]=nums1[m-1];
        break;
      }
      else{
        nums1[m+n-1]=nums2[n-1];
        //nums1[m+n]=nums2[n-1];
        n--;m--;
      }
    }
    return nums1;
}

bueno hice dos soluciones la primer despues de leer el enunciado :

function adherir(nums1,nums2,n,m){
    
    for (let i=m;i<m+n ;i++){
        nums1[i]=nums2[i-m];
        console.log("numero 1 : ",nums1[i-m]," numero 2 : ",nums2[i-m]);
    }
}

function ordenar(nums1,nums2,n,m){
    adherir(nums1,nums2,n,m)
    for (let i=1; i<nums1.length;i++){
        let temporal=nums1[i];
        let j=i-1;
      while(j>=0 && nums1[j]>temporal){
        nums1[j+1]=nums1[j];
          j--;    
      }
      nums1[j+1]=temporal;
    }
  return nums1;
};