PDF de programación - Algoritmos con Python - Arrays

Algoritmos con Python

Arrays

1 de marzo de 2021

Índice

1 Fusión de listas ordenadas

1.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Algoritmo en tiempo lineal
. . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Variante con k Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Suma sobre un rango

2.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Estructura de datos en O(1) por solicitud e inicialización en O(n) . . . . . . .

3 Duplicados en un rango

3.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Estructura de datos en O(1) por solicitud e inicialización en O(n) . . . . . . .

4 Suma máxima de los subarrays

4.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Algoritmo en O(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Consulta del mínimo de un árbol de segmentos de rango

5.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Estructura de datos con O(log n) por solicitud . . . . . . . . . . . . . . . . .
5.4 Análisis de la complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
2
2
3

4
4
4

5
5
5

6
6
6
6

7
7
7
7
8

6 Consultar suma sobre un rango--Árbol de Fenwick

10
6.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2 Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.3 Estructura de datos con O(log n) por solicitud . . . . . . . . . . . . . . . . . 10

7 Ventanas con k elementos distintos

13
7.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.2 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.3 Algoritmo en O(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.4 Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

I

Introducción

Los arrays figuran como uno de los tipos de datos elementales más importantes. Para mu-
chos problemas simples, no se requiere ninguna otra estructura de datos. En Python, los
arrays se almacenan en el tipo de datos llamado lista. La elección de este nombre puede
resultar confusa, porque las listas de Python no tienen nada que ver con las listas enla-
zadas, que son objetos estándar en C++ (std::list) y Java (LinkedList). Normalmente,
una lista enlazada permite eliminar o insertar un elemento determinado en una posición
determinada en tiempo constante. Sin embargo, insertar en una lista de Python requiere
construir en tiempo lineal una nueva lista que consta de un prefijo, el nuevo elemento y
un sufijo. Los elementos de una lista de Python se indexan desde 0. Esto debe tenerse en
cuenta al leer o mostrar datos, si alguna vez la numeración de los elementos comienza en
1 en el formato de las entradas o salidas.

En lo que sigue, usamos ’array’ como término genérico independiente del lenguaje, y
’lista’ cuando nos referimos a la estructura de datos específica de Python.

Se puede usar un array para representar un árbol binario de una manera muy simple. El
padre de un nodo en el índice i se encuentra en I/2, su hijo izquierdo en el índice 2i y
su hijo derecho en el índice 2i + 1. La raíz está en el índice 1 y el elemento en el índice 0
simplemente se ignora.

Esta sección trata sobre problemas clásicos en arrays y presenta estructuras de datos
para realizar operaciones en intervalos de índices conocidos como rangos, por ejemplo, el
cálculo de un valor mínimo dentro de un rango. Dos de las secciones describen estructuras
de datos dinámicas utilizadas para proporcionar operaciones eficientes de modificación de
elementos y consultas sobre dichos rangos.

1

1. Fusión de listas ordenadas

1.1. Definición

Dadas dos listas ordenadas x e y, producir una lista ordenada z, que contenga los elemen-
tos de x e y.

1.2. Aplicación

Esta operación es útil para el algoritmo de ordenación por fusión. Para ordenar una lis-
ta, la dividimos en dos partes de igual tamaño (hasta una diferencia de un elemento si
la longitud es impar). A continuación, las dos porciones se ordenan recursivamente y los
resultados ordenados se combinan mediante el procedimiento que se describe a continua-
ción. Este algoritmo tiene una complejidad óptima de O(n log n) comparaciones.

1.3. Algoritmo en tiempo lineal

La solución consiste en recorrer conjuntamente las dos listas e ir construyendo z a medida
que avanzamos. La clave es avanzar en cada paso dentro de la lista que tenga el elemento
actual más pequeño. Esto asegura que el propio resultado estará ordenado.

Figura 1: Fusión de listas

La fusión de dos listas funciona un poco como una cremallera con selección mínima en lugar de alternancia

def merge(x, y):

z = []
i = 0
j = 0
while i < len(x) or j < len(y):

if j == len(y) or i < len(x) and x[i] <= y[j]:

# priority on x

z.append(x[i])

2

i += 1

else:

z.append(y[j])
j += 1

return z

1.4. Variante con k Listas

# now y

Para identificar rápidamente la lista en la que tenemos que avanzar, podemos almacenar
los k elementos actuales de cada lista en una cola de prioridad. La complejidad es entonces
O(n log k) donde n es la longitud de la lista resultante.

3

2. Suma sobre un rango

2.1. Definición

Cada petición tiene la forma de un intervalo de índices [i,j) y debe devolver la suma de
los elementos de t entre los índices i (incluidos) y j (excluidos).

2.2. Estructura de datos en O(1) por solicitud e inicialización en

O(n)

Basta con calcular un array s de tamaño n + 1, que contiene todas las sumas de prefijos
de t. Más concretamente, s[j] = Σi<jt[i]. En particular, s[0] = 0, s[1] = t[0], s[n] =
Σn−1

i=0 t[i]. Entonces la respuesta a la petición [i,j) es s[j] - s[i].

4

3. Duplicados en un rango

3.1. Definición

Cada petición tiene la forma de un intervalo de índices [i,j) y debemos encontrar un
elemento x de t que aparezca al menos dos veces dentro de este intervalo o anunciar que
todos los elementos son distintos.

3.2. Estructura de datos en O(1) por solicitud e inicialización en

O(n)

Con un barrido de izquierda a derecha, construimos un array p indicando para cada j el
mayor índice i < j tal que t[i] = t[j]. Cuando t[j] se ve por primera vez, ponemos
p[j] = -1.

El cálculo de p requiere almacenar, para cada elemento x, el índice de la última aparición
de x observada en t durante el barrido. Esto puede hacerse con un array si se garantiza
el dominio de los elementos de t, o en su defecto con un diccionario basado en una tabla
hash.

Paralelamente, almacenamos en un array q, para cada j, el mayor valor de p[i] para todo
i j . En respuesta a una petición [i,j), si alguna vez q[j - 1] < i entonces todos los
elementos de [i,j) son distintos, en caso contrario t[q[j - 1]] es un duplicado.

Para determinar los índices de dos ocurrencias, basta con calcular en paralelo con q[j] el
índice i que realiza el máximo.

Figura 2: Encontrar duplicados

El algoritmo para encontrar duplicados en un ejemplo. En el intervalo [3,6) todos los elementos de t son
distintos porque q[5] < 3. Sin embargo, el intervalo [4,10) contiene duplicados, por ejemplo, b en las
posiciones q[9] y p[q[9]].

5

4. Suma máxima de los subarrays

4.1. Definición

Este problema estadístico busca encontrar, para un array de valores t, el máximo de t[i] +
t[i + 1] + ··· + t[j] sobre cada par de índices i,j con i j .

4.2. Algoritmo en O(n)

Esta solución por programación dinámica fue encontrada por Jay Kadane en 1984. Para
cada índice j buscamos la suma máxima t[i] + ··· + t[j] sobre todos los índices 0 i j
. Denotemos A[j] como este valor. Este valor debe ser el propio t[j], o estar formado por
t[j] más una suma de la forma t[i] + ··· + t[j − 1], que es a su vez máxima. Por tanto,
A[0] = t[0], ya que es la única opción, y para j 1, tenemos la relación de recurrencia
A[j] = t[j] + max{A[j - 1], 0}.

4.3. Variantes

Este problema se puede generalizar a las matrices. Dada una matriz M de dimensión n
x m, un rango de índices de fila [a,b] y un rango de índices de columna [i,j] definen
un rectángulo [a, b] ⊗ [i, j] dentro de la matriz. Queremos encontrar el rectángulo con la
mayor suma. Para ello, basta con hacer un bucle sobre todos los pares de índices de fila
[a, b], a b, y para cada par generar un array t de longitud m, tal que t[i] = M[a, i] +
··· + M[b, i]. Esta matriz puede obtenerse en tiempo O(m) a partir de la matriz de la
iteración anterior correspondiente al par [a, b - 1], simplemente añadiendo la fila b de
M. Con la ayuda del algoritmo anterior, podemos encontrar en tiempo O(m) un rango de
columnas [i,j] que describa un rectángulo [a, b]⊗ [i, j] de suma máxima acotada por las
filas a y b. La mayor suma observada al hacer un bucle sobre a y b da la suma máxima de
M. Este enfoque produce una solución con complejidad O(n2m).

6

5. Consulta del mínimo de un árbol de segmentos de

rango

5.1. Definición

Deseamos mantener una estructura de datos que almacene un array t de n valores y que
permita las siguientes operaciones:

Cambiar t[i] para un índice i dado.

Calcular minij<kt[j] para un rango dado de índices i,k.

5.2. Variante

Con sólo unos pequeños cambios también podemos determinar el índice del elemento
mínimo junto con su valor.

5.3. Estructura de datos con O(log n) por solicitud

La idea es complementar la matriz t con un árbol binario, conocido como árbol de segmen-
tos. Esta estructura de datos también se conoce como árbol BIT (Binary Index Tree). Cada
nodo es responsable de un rango de índices en t, véase la figura 3. El tamaño