Punto de equilibrio de la matriz

¿Cuál es la mejor manera de resolver esto? Un punto de equilibrio de una matriz A de elementos N es un índice i tal que todos los elementos en índices inferiores tienen valores < = A [i] y todos los elementos en índices más altos tienen valores mayores o iguales A [i].Punto de equilibrio de la matriz

Por ejemplo, dada:

A [0] = 4 A [1] = 2 A [2] = 7 A [3] = 11 A [4] = 9

una de las las soluciones correctas son: 2. Todos los elementos debajo de A [2] son menores que A [2], todos los elementos después de A [2] son más que A [2]. Una solución que me pareció es la solución O (nsquare). ¿Hay alguna solución mejor?

Fuente

2011-03-22 all_by_grace

Una idea que apareció es una solución O (nsquare), itera sobre la matriz, luego realiza una segunda iteración para verificar si la condición cumple o no. –

Solo quiero agregar un punto que, el punto de equilibrio puede no existir para una matriz dada de enteros. Por ejemplo, tome cualquier matriz de enteros ordenados en orden decreciente, es decir [4,3,2,1,0]. – Srikanth

Comience suponiendo A[0] es un poste. Luego comience a caminar la matriz; comparando cada elemento A[i] a su vez contra A[0], y también siguiendo el máximo actual.

Tan pronto como se encuentre un i tal que A[i] < A[0], ustedes saben que A[0] ya no puede ser un poste, y por extensión, tampoco puede hacerlo cualquiera de los elementos hasta e incluyendo A[i]. Entonces, continúe caminando hasta que encuentre el siguiente valor que es más grande que el máximo actual. Esto se convierte en el nuevo polo propuesto.

Por lo tanto, un O (n) solución!

En código:

int i_pole = 0; 
int i_max = 0; 
bool have_pole = true; 
for (int i = 1; i < N; i++) 
{ 
    if (A[i] < A[i_pole]) 
    { 
     have_pole = false; 
    } 
    if (A[i] > A[i_max]) 
    { 
     i_max = i; 
     if (!have_pole) 
     { 
      i_pole = i; 
     } 
     have_pole = true; 
    } 
}

Fuente

2011-03-22 21:59:09

Gracias. ¿Crees que hay alguna otra verificación que tengo que hacer? –

Si 'A = {0, 2, 1, 3, 5, 4, ...}', camina hasta el final y determina que 'A [0]' es un polo. Pero no sabe nada sobre los otros elementos, por lo que debe retroceder a 'A [1]' y comenzar de nuevo. En esta matriz cada tercer elemento es un polo y encontrarlos de esta manera toma O (n²). – aaz

Esto sigue siendo incorrecto. Para la entrada: [9, 5, 4, 3, 2, 8], devolverá el índice 4 (que tiene el valor 2). de hecho, todos los elementos del lado izquierdo de 2 son más grandes, lo que infringe la condición –

Si quieres saber donde todos los polos son, una O (n log n) solución sería la creación de una copia ordenada de la matriz, y mira a ver donde obtienes valores coincidentes.

EDITAR: Lo siento, pero esto en realidad no funciona. Un contraejemplo es [2, 5, 3, 1, 4].

Fuente

2011-03-22 22:15:49 Neil

+1: ¡Buena idea! –

Crear una lista de doble enlace como el i-ésimo nodo de esta lista contiene A[i] y i. Recorre esta lista mientras los elementos crecen (contando el máximo de estos elementos). Si alguno A[bad] < maxSoFar no puede ser MP. Quítelo y retroceda eliminando los elementos hasta que encuentre A[good] < A[bad] o llegue al encabezado de la lista. Continúe (comenzando con maxSoFar como máximo) hasta que llegue al final de la lista. Cada elemento en la lista de resultados es MP y cada MP está en esta lista. La complejidad es O (n) ya que se realiza un máximo de pasos para la matriz descendente - n pasos hacia adelante y n eliminaciones.

actualización

Oh, me confunde "cualquiera" con "todos" en la definición del problema :).

Fuente

2011-03-22 23:03:42 hoha

Crea dos matrices auxiliares, cada una con tantos elementos como la matriz de entrada, llamada MIN y MAX. Cada elemento M de MAX contiene el máximo de todos los elementos en la entrada desde 0..M. Cada elemento M de MIN contiene el mínimo de todos los elementos en la entrada de M..N-1.

Para cada elemento M de la matriz de entrada, compare su valor con los valores correspondientes en MIN y MAX. Si INPUT [M] == MIN [M] y INPUT [M] == MAX [M], M es un punto de equilibrio.

Building MIN toma N pasos, al igual que MAX. Luego, al probar la matriz, N tiene más pasos. Esta solución tiene una complejidad O (N) y encuentra todos los puntos de equilibrio. En el caso de la entrada clasificada, cada elemento es un punto de equilibrio.

Fuente

2011-03-23 00:22:06 bmcnett

En realidad, solo necesita compilar una de las matrices, ya que puede probar la matriz mientras computa la otra matriz y, por lo tanto, no necesita retener el resultado del cálculo. – Neil

sí, esa es la primera optimización que haría, también. – bmcnett

Puede combinar las respuestas de bmcnett y Oli para encontrar todos los polos lo más rápido posible.

std::vector<int> i_poles; 
i_poles.push_back(0); 
int i_max = 0; 
for (int i = 1; i < N; i++) 
{ 
    while (!i_poles.empty() && A[i] < A[i_poles.back()]) 
    { 
     i_poles.pop_back(); 
    } 
    if (A[i] >= A[i_max]) 
    { 
     i_poles.push_back(i); 
    } 
}

Puede utilizar una matriz preasignada al tamaño N si desea evitar las reasignaciones.

Fuente

2011-03-24 20:15:15 Neil

Una ventaja de construir matrices auxiliares MIN y MAX es que, suponiendo un paralelismo infinito, el algoritmo tiene complejidad O (logN) debido a que min y max son operadores asociativos. La mayoría de las computadoras hoy exhiben un paralelismo de más de 10,000 vías a través de la GPU y esto aumenta más rápido que la ley de Moore. – bmcnett

Respuesta

Cuestiones relacionadas