La forma más rápida de encontrar un producto mínimo de 2 elementos de matriz que contienen más de 200000 elementos

13

Tengo una matriz a[n]. El número nlo ingresamos nosotros. Necesito encontrar el producto mínimo de a[i]y a[j]si:

1) abs(i - j) > k

2) a[i] * a[j]se minimiza

Aquí está mi solución (muy ingenua):

#include <iostream>
using namespace std;
#define ll long long
int main() {
    ll n,k; cin >> n >> k;

    ll a[n]; for(ll i=0;i<n;i++) cin >> a[i];

    ll mn; bool first = true;

    for(ll i=0;i<n;i++) {
        for(ll j=0;j<n;j++) {
            if(i!=j)
            if(abs(i-j) > k) {
                if(first) {
                    mn = a[i]*a[j];
                    first = false;
                } else if(a[i]*a[j] < mn) mn = a[i]*a[j];
            }
        }
    }
    cout << mn << endl;
}

¿Pero quiero saber si hay alguna forma más rápida de encontrar un producto mínimo con distancia?

Mouvre
fuente
77
¿Por qué no debería #incluir <bits / stdc ++. H>? y C ++ solo proporcionan una matriz de longitud variable por extensión del compilador. ¿Por qué no estás usando std::vector? @Scheff: la clasificación destruiría las relaciones originales de "distancia".
David C. Rankin
3
Al menos el cheque if (i!=j) if (abs(i - j) > k)puede ser eliminado. Sólo empezar el bucle interior en i + k + 1: for (ll j = i + k + 1; j < n; ++j). La verificación con también firstse puede eliminar si mnse inicializa antes, por ejemplo, con mn = a[0] * a[k + 1];. (Tal vez, kdebería verificarse ninicialmente para hacer esto a prueba de balas). Pero sigue siendo O (N²). Esto debe ser factible más rápido ...
Scheff
2
@PaulMcKenzie Por favor, muestre una consulta con no menos de dos resultados útiles entre los primeros diez para un producto mínimo con distancia de índice (o máximo).
barba gris el
1
@PaulMcKenzie "Probablemente hay cientos, si no miles de enlaces URL que muestran respuestas a esta pregunta". - comparta al menos tres de estas URL.
עדלעד ברקן
2
¿De dónde vino esta pregunta? No suena como algo hecho de la nada. No me sorprendería que sea de uno de esos sitios de "jueces en línea". Si es así, en esos sitios probablemente haya discusiones prolongadas sobre la solución del problema, si no soluciones completas.
PaulMcKenzie

Respuestas:

12

Suponiendo que haya al menos un par de elementos que satisfagan las condiciones y que no se desborde la multiplicación de dos elementos, esto puede hacerse en el Theta(n-k)tiempo y el Theta(1)espacio en el peor y el mejor de los casos, con algo como esto:

auto back_max = a[0];
auto back_min = a[0];
auto best = a[0]*a[k+1];

for(std::size_t i=1; i<n-(k+1); ++i) {
    back_max = std::max(back_max, a[i]);
    back_min = std::min(back_min, a[i]);
    best = std::min(best, std::min(a[i+k+1]*back_max, a[i+k+1]*back_min));
}

return best;

Esto es óptimo en términos de la complejidad asintótica del peor de los casos, tanto para el tiempo como para el espacio, porque el producto óptimo puede estar a[0]con cualquiera de los n-(k+1)elementos en la distancia, al menos k+1, por lo n-(k+1)que cualquier algoritmo que resuelva el problema debe leer al menos los enteros.


La idea detrás del algoritmo es la siguiente:

El producto óptimo utiliza dos elementos de a, suponga que estos son a[r]y a[s]. Sin pérdida de generalidad podemos suponer que s > rdado que el producto es conmutativo.

Debido a la restricción, abs(s-r) > kesto implica que s >= k+1. Ahora spodría ser cada uno de los índices que satisfagan esta condición, por lo que iteramos sobre estos índices. Esa es la iteración ien el código que se muestra, pero se cambia por k+1conveniencia (realmente no importa). Para cada iteración, necesitamos encontrar el producto óptimo que incluya el i+k+1mayor índice y compararlo con la mejor estimación anterior.

Los índices posibles para emparejar i+k+1son todos índices menores o iguales idebido al requisito de distancia. Tendríamos que repetir todo esto también, pero eso es innecesario porque el mínimo de a[i+k+1]*a[j]over jen fijo ies igual a min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))debido a la monotonicidad del producto (tomando el mínimo con respecto al mínimo y al máximo sobre a[j]cuentas para los dos posibles signos de, a[i+k+1]o equivalentemente, las dos posibles direcciones de monotonicidad.)

Dado que el conjunto de a[j]valores sobre el que optimizamos aquí es justo {a[0], ..., a[i]}, que simplemente crece por un elemento ( a[i]) en cada iteración de i, simplemente podemos realizar un seguimiento de max(a[j])y min(a[j])con variables individuales actualizándolas si a[i]es mayor o menor que los valores óptimos anteriores. Esto se hace con back_maxy back_minen el ejemplo de código.

El primer paso de la iteración ( i=0) se omite en el bucle y, en su lugar, se realiza como inicialización de las variables.

nuez
fuente
3
@greybeard No necesito mantenerlos cerca, porque los únicos posibles candidatos para un producto óptimo a[i+k+1]son el mínimo y el máximo.
nogal
¿Podría explicar por qué el algoritmo funciona en su respuesta?
MinaHany
6

No estoy seguro sobre lo más rápido .

Para el problema más simple sin i <j - k , el producto mínimo se encuentra entre los productos de pares de los dos elementos más pequeños y más grandes.

Entonces, (lo siguiente es demasiado complicado, ver la respuesta de nuez )
(• rechazar si k ≤ n
  • inicializar minProduct a a [0] * a [k + 1])

  • mantenga dos estructuras de datos dinámicas minmax upToI y beyondIplusK
    comenzando con {} y {a [ j ] | kj }
  • para cada i de 0 a n - k - 1
    • agregue un [ i ] a upToI
    • eliminar un [ i + k ] de beyondIplusK
    • compruebe si hay un nuevo producto mínimo entre
      min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
      max ( upToI ) × min ( beyondIplusK ) y max ( upToI ) × max ( beyondIplusK )
barba gris
fuente
Este debería ser el más rápido, al menos en cuanto a complejidad. Es O (n) tiempo y almacenamiento.
smttsp
la solución original tiene la complejidad O (N ** 2), ¿cómo estima la complejidad de su solución?
lenik
O (nlogn) tiempo, O (n) espacio (para implementaciones mínimas adecuadas)
barba
@anciano. ¿Por qué necesitas tiempo n * logn? ¿Por qué no simplemente mantener una matriz n * 4 que contiene minUpto, maxUpto, minBeyond, maxBeyond(Se puede crear en dos iteraciones)? Luego, en la tercera iteración, para cada índice, encuentre la multiplicación mínima posible.
smttsp
(@smttsp Ese sería un paso alternativo en la dirección de la solución de nuez .)
barba gris el
4

Para "magnitud mínima"

Encuentre los 2 elementos de "magnitud más pequeña" y luego (después de haber encontrado dos ceros o buscado en toda la matriz), multiplíquelos.

Para el "valor más bajo" sin la abs(i - j) > kparte

Hay 3 posibilidades:

  • los dos números negativos más altos (magnitud más pequeña)

  • los dos números no negativos más bajos (magnitud más pequeña)

  • el número negativo más bajo (magnitud más grande) y el número no negativo más alto (magnitud más grande)

Puede buscar los 6 valores y descubrir los productos y cuál es el mejor al final.

Sin embargo; tan pronto como vea un cero, sabe que no necesita saber más acerca de las 2 primeras posibilidades; y tan pronto como veas un número negativo y uno no negativo, sabrás que solo te importa la tercera posibilidad.

Esto lleva a una máquina de estados finitos con 3 estados: "preocuparse por las 3 posibilidades", "la respuesta es cero a menos que se vea un número negativo" y "solo preocuparse por la última posibilidad". Esto se puede implementar como un conjunto de 3 bucles, donde 2 de los bucles saltan a ( goto) el centro de otro bucle cuando cambia el estado (de la máquina de estados finitos).

Específicamente, podría parecerse a algo vagamente (no probado):

   // It could be any possibility

   for(ll i=0;i<n;i++) {
       if(a[i] >= 0) {
            if(a[i] < lowestNonNegative1) {
                lowestNonNegative2 = lowestNonNegative1;
                lowestNonNegative1 = a[i];
            }
            if(lowestNonNegative2 == 0) {
                goto state2;
            }
       } else {
            if(a[i] > highestNegative1) {
                highestNegative2 = highestNegative1;
                highestNegative1= a[i];
            }
            if(lowestNonNegative1 < LONG_MAX) {
                goto state3;
            }
       }
   }
   if(lowestNonNegative2 * lowestNonNegative1 < highestNegative2 * highestNegative1) {
       cout << lowestNonNegative2 * lowestNonNegative1;
   } else {
       cout << highestNegative2 * highestNegative1;
   }
   return;

   // It will be zero, or a negative and a non-negative

   for(ll i=0;i<n;i++) {
state2:
       if(a[i] < 0) {
           goto state3;
       }
   }
   cout << "0";
   return;

   // It will be a negative and a non-negative

   for(ll i=0;i<n;i++) {
state3:
       if(a[i] < lowestNegative) {
           lowestNegative = a[i];
       } else if(a[i] > highestNonNegative) {
           highestNonNegative = a[i];
       }
    }
    cout << lowestNegative * highestNonNegative;
    return;

Para el "valor más bajo" con la abs(i - j) > kparte

En este caso todavía tienes las 3 posibilidades; y podría hacerlo funcionar con el mismo enfoque de "3 bucles con máquina de estados finitos", pero se vuelve demasiado desordenado / feo. Para este caso, es probable que una mejor alternativa escanee previamente la matriz para determinar si hay ceros y si todos son negativos o todos positivos; para que después de la exploración previa pueda saber si la respuesta es cero o seleccionar un bucle diseñado solo para la posibilidad específica.

Brendan
fuente
1
¿Dónde explica esto el límite inferior k en la diferencia de índice?
barba gris el
1
@greybeard: no lo hace (me perdí esa parte): el código debería modificarse para tenerlo en cuenta.
Brendan
¿Por qué necesitarías dos ceros?
TrentP
@TrentP: Argh, tienes razón. Un cero es suficiente para saber que la respuesta es 0 o un número negativo.
Brendan