algorithm - superior - Dada la matriz y la clave, ¿encuentra la cantidad de elementos más pequeños o iguales que ella en su matriz secundaria izquierda y derecha?

recorrer diagonales matriz java

Question

Tengo que encontrar la cantidad de elementos menores o iguales al i -ésimo elemento de la matriz en los subarreglos izquierdo y derecho.

Por ejemplo, si mi matriz es

A[]=4 3 5 2 2 5

Mis 2 arreglos serán

0 0 2 0 0 5

Y

3 2 3 1 1 0

El i -ésimo elemento de la 1ra matriz denota la cantidad de elementos menores que o igual a i -ésimo elemento a la izquierda del i -ésimo elemento.

El i -ésimo elemento de la 2da matriz denota la cantidad de elementos menores o iguales a i -ésimo elemento a la derecha del i -ésimo elemento.

Puedo encontrar estas matrices en O ( n ² ) usando dos bucles.

¿Se puede hacer esto en O ( n )?

Answer 1

No, no es posible hacerlo en el tiempo O(n) . Lo mejor que puedes hacer es O(n log n) .

Aquí está la prueba. Supongamos que la matriz original tiene n elementos distintos . Veamos cuántas posibilidades hay para la primera matriz que desea (la prueba para la otra es similar). Hay 1 posibilidad para el primer número ( 0 ). Hay 2 posibilidades para el segundo número ( 0 o 1 ). Hay 3 posibilidades para el 3er número ( 0 , 1 o 2 ), y así sucesivamente. Se deduce que hay como máximo 1 * 2 * 3 * ... * n = n! respuestas posibles. De hecho, es fácil ver que para cada una de estas posibles respuestas hay al menos una matriz de números distintos que la producen (Trabaje de izquierda a derecha. Si la answer[i] es 0 , configure el original[i] como más pequeño que todos los números elegidos previamente. Si la answer[i] es i , configure el original[i] como mayor que todos los números previamente seleccionados. De lo contrario, configure el original[i] como un número entre el i -ésimo más pequeño y el (i+1) -el número más pequeño ya elegido). Cualquier algoritmo debe identificar cuál de los n! posibles respuestas es la correcta. Si siempre podemos terminar el algoritmo con comparaciones f(n) se deduce que 2^f(n) >= n! (cada comparación tiene solo 2 resultados posibles ya que los números originales fueron todos distintos). Tomando registros (base 2) de ambos lados obtenemos f(n) >= log(n!) . Utilizando la aproximación de Stirling para log(n!) Vemos que no podemos hacer mejor que las comparaciones O(n log n) .

Es posible hacerlo en tiempo O(n log n) . El siguiente método Java (que no se ejecuta en tiempo O(n log n) ) devuelve la primera matriz que necesita (la segunda se puede hacer de manera similar). Arrays.sort() usa TimSort que es O(n log n) . Sin embargo, para hacer que todo el método se ejecute en tiempo O(n log n) , debe reemplazar ArrayList con una implementación de List donde los métodos add(Object object) , remove(int index) y lastIndexOf(Object object) todos ejecutar en tiempo O(log n) . De acuerdo con http://www.nayuki.io/page/avl-tree-list , AvlTreeList add() y remove() en el tiempo O(log n) , y es posible "aumentar" una lista AvlTreeList para que las búsquedas son O(log n) también. Esto demuestra que sus matrices se pueden encontrar en el tiempo O(n log n) .

public static int[] firstArray(int[] arr) {
    int[] copy = arr.clone();
    Arrays.sort(copy);
    List<Integer> list = new ArrayList<>();
    for (int a : copy)
        list.add(a);
    int length = arr.length;        
    int[] temp = new int[length];
    for (int i = length - 1; i >= 0; i--) {
        int j = list.lastIndexOf(arr[i]);
        temp[i] = j;
        list.remove(j);
    }
    return temp;
}

Answer 2

Simplificaré la respuesta de @ pbabcdefp utilizando algo llamado árbol binario equilibrado con campo de rango (ver Knuth 6.2.3, Representación de la lista lineal). Considere un árbol equilibrado (la implementación no importa, por lo tanto, rojo-negro o AVL funcionará bien), pero tenemos un campo adicional llamado rank que almacenará el tamaño del subárbol izquierdo , los números se insertarán en nuestro árbol en orden de menor a mayor, el campo de clasificación para cada nodo afectado se actualiza después de cada inserción / rotación. Permitiremos elementos duplicados en nuestro árbol equilibrado.

Algoritmo A:

1. Establecer la head en el nodo raíz. Establezca v al valor que estamos buscando. Deje que sea el índice en la lista para v , este será nuestro valor de retorno.
2. Si la head es nula / vacía, regrese con éxito con el índice i .
3. Si v < head.value , then head <- head.left , de lo contrario i <- i + head.rank + 1 y head <- head.right .
4. Regrese a 2.

Algoritmo Original :

Para cada elemento de la matriz: utilice el algoritmo A descrito anteriormente para encontrar el número de elementos (que están en el árbol y, por lo tanto, antes del elemento actual) menor o igual a él, y luego agréguelo a nuestro árbol utilizando la inserción modificada. Esto da la primera matriz. Repita una vez más, esta vez caminando sobre la matriz hacia atrás en lugar de hacia adelante, para obtener la segunda matriz.

Answer 3

Parece que no puedes saltar sobre nlogn para que la versión básica sea justa:

def naive(arr)
  res = Array.new(arr.size,0)
  for i in 0..arr.length-1
    for j in i+1..arr.length-1
      res[i] += 1 if arr[i] >= arr[j]
    end
  end
  res
end

Sin embargo, dependiendo de sus conjuntos de datos, puede hacer algunas optimizaciones. Por ejemplo, en su ejemplo hay repeticiones; podemos usar ese hecho para evitar el desplazamiento de la matriz para el mismo número dos veces. En tal caso, en lugar de buscar números menores que el actual, puede hacer además de cada número más grande que el actual (de derecha a izquierda) e ignorar los números que ya se han utilizado:

def rightleft(arr)
  ignore = {}
  res = Array.new(arr.size,0)
  (arr.size-1).downto(0) do |i|
    current = arr[i]
    next if ignore[current]
    additor = 1
    (i-1).downto(0) do |j|
      if arr[i] <= arr[j]
        res[j] += additor
          if arr[i] == arr[j]
          additor += 1
          ignore[current] = true
        end
      end
    end
  end
  res
end

Tomemos un ejemplo con muchas repeticiones:

A = %W{1 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 7 8 9 3 5 4 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 7 8 9 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 12 14 5 6 4 3 1 7 8 9 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 12 14 5 6 4 3 1 7 8 9 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 7 8 9 1 10 2 11 12 4 13 14 6 15 12 16 17 18 19}.map(&:to_i)

Ahora punto de referencia

puts "NAIVE 100 times:"
puts time_elapsed{
  100.times do
    naive(A)
  end
}

puts "rl 100 times"
puts time_elapsed{
  100.times do
    rightleft(A)
  end
}

Resultado:

NAIVE 100 times:
[14, 30, 29, 53,...., 0, 0]
Time elapsed 485.935997 milliseconds

rl 100 times
[14, 30, 29, 53,...., 0, 0]
Time elapsed 81.735048 milliseconds

Pero cuando no tiene repeticiones, esta optimización lo hará un poco más lento. Aquí hay resultados para los números 1,2,3 ..., 99,100 mezclados:

NAIVE 100 times:
[70, 7,... 1, 0]
Time elapsed 99.58762899999999 milliseconds

rl 100 times
[70, 7, ... 1, 0]
Time elapsed 113.186392 milliseconds

Answer 4

Puede hacer esto en O (nlogm) (donde n es la longitud de A, y m es el tamaño del elemento más grande en la matriz) utilizando un Fenwick Tree .

Un árbol de Fenwick (también llamado árbol indexado binario) le permite agregar elementos a una matriz y calcular sumas de elementos consecutivos en el tiempo O (logn). Hay un buen tutorial en topcoder .

En este problema, podemos usar el árbol de Fenwick para almacenar un histograma de cuántas veces hemos visto cada valor. El histograma comienza vacío, y luego gradualmente insertamos elementos en el histograma.

Entonces, necesitamos iterar a través de la matriz, cada vez primero calculando cuántos elementos tienen un valor más pequeño que el valor actual, y luego agregando el valor actual a la matriz.

Código de Python:

def find_lower(A):
    """Return B where B[i] is the number of elements <= A[i] in A[0:i]"""
    top = max(A) + 1
    F = fenwick_new(top)
    left = []
    for a in A:
        left.append( fenwick_sum(F,a) )
        fenwick_increase(F,a,1)
    return left

A=[4, 3, 5, 2, 2, 5]
print find_lower(A)
print find_lower(A[::-1])[::-1]

Esto usa algunas funciones de árbol estándar de Fenwick:

def fenwick_new(m):
    """Create empty fenwick tree with space for elements in range 0..m"""
    # tree[i] is sum of elements with indexes i&(i+1)..i inclusive
    return [0] * (m+1)

def fenwick_increase(tree,i,delta):
    """Increase value of i-th element in tree by delta"""
    while i < len(tree):
        tree[i] += delta
        i |= i + 1

def fenwick_sum(tree,i):
    """Return sum of elements 0..i inclusive in tree"""
    s = 0
    while i >= 0:
        s += tree[i]
        i &= i + 1
        i -= 1
    return s