arrays - tutorial - Encuentra mínimos locales en una matriz

multiplicacion de matrices numpy

Question

Dada una matriz de enteros, encuentra los mínimos locales. Un elemento A [i] se define como un mínimo local si A [i-1]> A [i] y A [i] <A [i + 1] donde i = 1 ... n-2. En el caso de elementos de límite, el número debe ser más pequeño que su número adyacente.

Sé que si solo hay un mínimo local, entonces podemos resolver con la búsqueda binaria modificada. Pero si se sabe que existen múltiples mínimos locales en la matriz, ¿se puede resolver en tiempo O(log n) ?

Answer 1

Aquí hay una solución que funciona en O (log n). Básicamente, esto funciona en el enfoque de clasificación de fusión (dividir y conquistar).

public class LocalMaxima {
int []a = {5,8,10,25,6,3,44,51,55,56,57,58,34,5,59};
@Test
public void localMaxima () {
System.out.println((a[localMaxima(0,a.length-1)]));
}
int localMaxima(int low, int high) {
if(high-low > 2) {
int mid = (low+high)/2;
return maxof(localMaxima(low,mid),localMaxima(mid+1, high));
}
else if(high-low == 1) {
return maxof(high,low);
}
else if(high-low == 0) {
return high;
}
if(high-low == 2) {
return maxof(maxof(low, high),low+1);
}
return 0;
}
int maxof(int i, int j) {
if(a[i] <a[j]) {
return j;
}
else {
return i;
}
}
}

Answer 2

El número de mínimos locales puede ser n/2 ; no puede enumerarlos todos en O(log n) tiempo.

Answer 3

En realidad, mi algoritmo anterior se puede modificar para obtener todos los máximos en tiempo O (log n). Probé que funciona muy bien para todas las entradas proporcionadas. Por favor, hágamelo saber sus comentarios

public class LocalMaximas {
@Test
public void test () {
System.out.println("maximas: please modify code to handle if array size is <= 2");
int []a = {5,8,10,25,6,3,44,51,55,56,57,58,34,5,59,2};
localMaximas(a);
int []b = {9,7,2,8,5,6,3,4, 2}; //9,8,6,4
localMaximas(b);
int [] c= {15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1};//15,20
localMaximas(c);
}
public void localMaximas (int [] a) {
System.out.println("/n/n");
if(isMaxima(a,0)) {
System.out.println(a[0]);
}
if(isMaxima(a,a.length-1)) {
System.out.println(a[a.length-1]);
}
localMaximas(a,0,a.length-1);
}
int localMaximas(int []a,int low, int high) {
int mid = (low+high)/2;
if(high-low > 3) { // more than 4 items in currently divided array
if(isMaxima(a,mid)) {
System.out.println(a[mid]);
}
localMaximas(a,low, mid);
localMaximas(a,mid, high);
}
else if(high-low == 3){ //exactly 4 items in currently divided array
localMaximas(a,low, mid+1);
localMaximas(a,mid, high);
}
else if((high-low == 2) && (isMaxima(a,low+1))) {
System.out.println(a[low+1]);
}
return 0;
}
int maxof(int []a, int i, int j) {
if(a[i] <a[j]) {
return j;
}
else {
return i;
}
}
boolean isMaxima(int []a ,int mid) {
if(mid == 0) {
if(maxof(a, mid, mid+1) == mid) {
return true;
}
else {
return false;
}
}
else if(mid==a.length-1) {
if(maxof(a,mid,mid-1) == mid) {
return true;
}
else {
return false;
}
}
else {
if((maxof(a, mid, mid+1) == mid) && (maxof(a, mid, mid-1) == mid)) {
return true;
}
else {
return false;
}
}
}
}

Answer 4

La pregunta original no está completa.

¡Acabo de encontrar la pregunta completa y la explicación completa en Encontrar los mínimos locales en una matriz ! - no es mi blog

Dada una matriz de enteros únicos cuyos primeros dos números están disminuyendo y los últimos dos números están aumentando, encuentre un número en la matriz que sea el mínimo local. Un número en la matriz se llama mínimos locales si es más pequeño que sus números izquierdo y derecho.

Por ejemplo, en la matriz 9,7,2,8,5,6,3,4 2 es un mínimo local ya que es más pequeño que su número derecho e izquierdo 7 y 8. Del mismo modo, 5 es otro mínimo local ya que está entre 8 y 6, ambos más grandes que 5.

Necesitas encontrar uno de los mínimos locales.

Answer 5

Si no se garantiza que los elementos de la matriz sean distintos, no es posible hacerlo en tiempo O (log n). El motivo de esto es el siguiente: suponga que tiene una matriz donde todos los valores n> 1 son iguales. En este caso, ninguno de los elementos puede ser mínimos locales, porque ningún elemento es menor que sus vecinos. Sin embargo, para determinar que todos los valores son iguales, tendrá que mirar todos los elementos de la matriz, lo que lleva tiempo O (n). Si usa menos de O (n), no necesariamente puede mirar todos los elementos de la matriz.

Si, por otro lado, se garantiza que los elementos de la matriz serán distintos, puede resolver esto en tiempo O (log n) utilizando las siguientes observaciones:

1. Si solo hay un elemento, se garantiza que es un mínimo local.
2. Si hay varios elementos, mira el elemento del medio. Si es un mínimo local, ya está. De lo contrario, al menos uno de los elementos al lado debe ser más pequeño que él. Ahora, imagina lo que sucedería si empezaras en uno de los elementos más pequeños y avanza progresivamente hacia uno de los extremos de la matriz en la dirección alejada del elemento central. En cada paso, el siguiente elemento es más pequeño que el anterior, o será más grande. Eventualmente, golpeará el final de la matriz de esta manera o alcanzará un mínimo local. Tenga en cuenta que esto significa que puede hacer esto para encontrar un mínimo local. Sin embargo, en realidad no vamos a hacer eso. En su lugar, usaremos el hecho de que existirá un mínimo local en esta mitad de la matriz como una justificación para desechar la mitad de la matriz. En lo que queda, tenemos la garantía de encontrar un mínimo local.

En consecuencia, puede construir el siguiente algoritmo recursivo:

1. Si solo hay un elemento de matriz, es un mínimo local.
2. Si hay dos elementos de matriz, compruebe cada uno. Uno debe ser un mínimo local.
3. De lo contrario, mira el elemento central de la matriz. Si es un mínimo local, devuélvalo. De lo contrario, al menos un valor adyacente debe ser menor que este. Recuerda en la mitad de la matriz que contiene ese elemento más pequeño (pero no en el medio).

Note que esto tiene la relación de recurrencia.

T (1) ≤ 1

T (2) ≤ 1

T (n) ≤ T (n / 2) + 1

Usando el teorema maestro, puede mostrar que este algoritmo se ejecuta en el tiempo O (log n), según se requiera.

¡Espero que esto ayude!

Tenga en cuenta que este algoritmo solo funciona si los bordes de la matriz cuentan como mínimos locales si son más pequeños que el elemento adyacente.

Answer 6

Tu algoritmo no funcionará para esta matriz

15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1

Aquí el mínimo local es 12 ... pero cuando verifico el elemento medio, que es 7, el algoritmo descartará la mitad izquierda (que tiene el mínimo) y verificará la mitad derecha. Por lo tanto no funciona

Creo que solo funcionará en el caso especial cuando la matriz tiene una propiedad especial que A [1] ≥ A [2] y A [n - 1] ≤ A [n].

Answer 7

Utilice un algoritmo de dividir y conquistar. Sea m = n / 2 y examine el valor A [m] (es decir, el elemento en el centro de la matriz).

Caso 1: A [m − 1] <A [m]. Luego, la mitad izquierda de la matriz debe contener un mínimo local, por lo tanto recuérdese en la mitad izquierda. Podemos mostrar esto por contradicción: supongamos que A [i] no es un mínimo local para cada 0 ≤ i <m. Entonces, A [m-1] no es un mínimo local, lo que implica que A [m-2] <A [m-1]. De manera similar, A [m −3] <A [m −2]. Continuando de esta manera, obtenemos A [0] <A [1]. Pero entonces A [0] es un mínimo local, contrariamente a nuestro supuesto inicial.

Caso 2: A [m + 1]> A [m]. Luego, la mitad derecha de la matriz debe contener un mínimo local, por lo tanto recuérdese en la mitad derecha. Esto es simétrico al caso 1.

Caso 3: A [m - 1]> A [m] y A [m + 1] <A [m]. Entonces A [m] es un mínimo local, así que devuélvalo. La recurrencia del tiempo de ejecución es T (n) = T (n / 2) + Θ (1), que produce T (n) = Θ (log n).