$k$-ésimo número en $N \times M$ tabla

Question

Dado un array $A$, donde $A[i][j] = i\times j$ y $1 \leq i \leq N, 1 \leq j \leq M$, entonces ¿cuál es la mejor manera de encontrar el # de $k$-ésimo número en esta matriz, si los ordena en una sola matriz en aumentar el valor?

Answer 1

Una pregunta muy interesante. Pensé que debería ser posible para esto escribimos en "forma cerrada" - aquí el sentido de que debería ser posible calcular en la constante de tiempo. No pude hacerlo, pero aún así creo que podría ser posible - tal vez basada en A000005, A061017, o la derivada como A006218...

Hasta que alguien encuentra una forma cerrada: Cada valor de $a$ aparece en la matriz, cuando puede ser escrito como $a = i\cdot j$$i \leq N$$j \leq M$. Ahora la idea es contar el número de divisores $i,j$ de cada valor de $a = 1 ... k$) que satisfacen este criterio (el $k$ aquí es sólo un límite superior). Estos números se pueden sumar, hasta que la suma sea mayor o igual a $k$. El actual $a$ es el valor que hemos estado buscando.

La asintótica en el tiempo de ejecución de este debe ser $\mathcal{O}(kM)$.

Aquí está la solución de fuerza bruta (con la clasificación) y la solución de conteo de los divisores, implementado en Java, para aquellos que estén interesados.

import java.util.Arrays;

public class KthEntryTest
{
    public static void main(String[] args)
    {
        for (int N=1; N<=10; N++)
        {
            for (int M=1; M<=10; M++)
            {
                for (int k=1; k<=M*N; k++)
                {
                    int resultA = computeBruteForce(N, M, k);
                    int resultB = computeByCount(N, M, k);
                    System.out.println("N="+N+", M="+M+", k="+k+", resultA="+resultA+", resultB="+resultB);
                    if (resultA != resultB)
                    {
                        System.out.println("ERROR!");
                    }
                }
            }
        }
    }

    private static int computeBruteForce(int N, int M, int k)
    {
        int A[][] = new int[N][M];
        for (int i=1; i<=N; i++)
        {
            for (int j=1; j<=M; j++)
            {
                A[i-1][j-1] = i*j;
            }
        }
        int a[] = flatten(A); 
        Arrays.sort(a);
        return a[k-1];
    }


    private static int[] flatten(int A[][])
    {
        int N = A.length;
        int M = A[0].length;
        int result[] = new int[N*M];
        for (int i=0; i<N; i++)
        {
            System.arraycopy(A[i], 0, result, i*M, M);
        }
        return result;
    }

    private static int computeByCount(int N, int M, int k)
    {
        int sum = 0;
        for (int i=1; i<=k; i++)
        {
            int count = 0;
            for (int j=1; j<=M; j++)
            {
                if (i%j == 0)
                {
                    int d = i/j;
                    if (d <= N)
                    {
                        count++;
                    }
                }
            }
            sum += count;
            if (sum >= k)
            {
                return i;
            }
        }
        return -1;
    }
}

Answer 2

Problema Interesante :)
Podemos resolver mediante búsqueda binaria como Ross Milikan indicado.
La principal cosa que queda es encontrar a $n(p)$ que se puede hacer simplemente en $O(M)$ complejidad , donde
$$n(p) = \sum_{i=1}^M min(floor(p/i),N)$$

La lógica que se usa aquí es encontrar el número de elementos menos de o igual a $p$ $jth$ columna , que será equivalente a $min(floor(p,i),N)$ .

Esto proviene del hecho de que el número de múltiplos de $i$ menos que en igual a $p$ es igual a $floor(p,i)$ y tomamos mínimo desde una columna puede contener como máximo) $N$ elementos.

Así , podemos resolver este en $O(M log (NM))$ .

Answer 3

Sugerencia para cualquier persona que tiene más tiempo que yo: parece que si, $A[i][j]$ $k$- ésimo término luego de la $(k+1)$-ésimo término es un vecino de $A[i][j]$. En cuyo caso puede ser posible hacer esto en $\mathcal{O}(k)$ mediante el uso de un algoritmo recursivo.

---

Que no, aquí es un ingenuo solución:

• Construcción $\tilde{A}$ que es la esquina superior izquierda $\min(N,k)\times\min(M,k)$ matriz de $A$.
• Sort $\tilde{A}$ en una sola matriz $B$.
• Quicksort $B$.
• Elegir el $k$-ésimo elemento de la ordenó $B$.

El cuello de botella es el quicksort, que es, en promedio, $\mathcal{O}(NM\log(NM))$.

Answer 4

Esto es básicamente en la selección de Jóvenes tableaux, y también la selección en X+Y ordenados SUMA de la matriz de toma de $X[i] = Y[i] = \log i$, las sumas de ser $S[i,j] = \log i + \log j$), el último de los cuales ha conocido a $O(M+N)$ tiempo de algoritmos para la selección de la $k^{th}$ elemento más grande.

Este papel: Generalizar la Selección y Clasificación: se Ordenan las Matrices tiene un $O(M+N)$ tiempo para el algoritmo de sumas ordenadas de selección.

Una explicación de este algoritmo (llamado el FJ-Algoritmo, por las iniciales de los autores, el papel más arriba) puede encontrarse en la sección 2 de este documento: memoria Caché ajeno selección ordenada X+Y matrices.