arrays - sencillos - Dados 2 arreglos ordenados de enteros, encuentre el número n más grande en tiempo sublineal

imprimir un arreglo en c

Question

Posible duplicado:
¿Cómo encontrar el elemento kth más pequeño en la unión de dos matrices ordenadas?

Esta es una pregunta que uno de mis amigos me dijo que le preguntaron mientras estaba entrevistando. He estado pensando en una solución.

El tiempo sublime me implica logarítmico, así que quizás algún tipo de método de dividir y conquistar. Para simplificar, digamos que ambas matrices son del mismo tamaño y que todos los elementos son únicos

Answer 1

¿Sublinear de qué? No puede tener un algoritmo que no compruebe al menos n elementos, incluso verificar que una solución requiera verificar tantos. Pero el tamaño del problema aquí seguramente debe significar el tamaño de las matrices, por lo que un algoritmo que solo verifica n elementos es sublineal.

Así que creo que no hay truco aquí, comience con la lista con el elemento de inicio más pequeño y avance hasta que usted:

1. Alcanza el elemento n, y listo.
2. Encontrar el siguiente elemento es más grande que el siguiente elemento en la otra lista, en cuyo punto cambia a la otra lista.
3. Quedarse sin elementos y cambiar.

Answer 2

Creo que puedes resolver este problema usando una variante en la búsqueda binaria. La intuición detrás de este algoritmo es la siguiente. Deje que las dos matrices sean A y B, y supongamos por simplicidad que tienen el mismo tamaño (esto no es necesario, como verá). Para cada matriz, podemos construir matrices paralelas Ac y Bc de tal manera que para cada índice i, Ac [i] es el número de elementos en las dos matrices que no son más grandes que A [i] y Bc [i] es el número de elementos en las dos matrices que no son más grandes que B [i]. Si pudiéramos construir estos arreglos de manera eficiente, entonces podríamos encontrar el elemento kth más pequeño de manera eficiente haciendo búsquedas binarias tanto en Ac como en Bc para encontrar el valor k. La entrada correspondiente de A o B para esa entrada es el kth elemento más grande. La búsqueda binaria es válida porque las dos matrices Ac y Bc están ordenadas, lo cual creo que puedes convencerte fácilmente.

Por supuesto, esta solución no funciona en tiempo sublineal porque toma O (n) tiempo para construir las matrices Ac y Bc. La pregunta entonces es: ¿hay alguna forma en que podamos construir implícitamente estas matrices? Es decir, ¿podemos determinar los valores en estas matrices sin construir necesariamente cada elemento? Creo que la respuesta es sí, utilizando este algoritmo. Comencemos buscando en la matriz A para ver si tiene el valor kth más pequeño. Sabemos a ciencia cierta que el valor más pequeño kth no puede aparecer en la matriz en el array A después de la posición k (suponiendo que todos los elementos son distintos). Entonces, concentrémonos solo en los primeros k elementos de la matriz A. Haremos una búsqueda binaria sobre estos valores de la siguiente manera. Comience en la posición k / 2; este es el elemento más pequeño k / 2 en la matriz A. Ahora haga una búsqueda binaria en la matriz B para encontrar el valor más grande en B más pequeño que este valor y observe su posición en la matriz; este es el número de elementos en B más pequeño que el valor actual. Si sumamos la posición de los elementos en A y B, tenemos el número total de elementos en los dos arreglos más pequeños que el elemento actual. Si esto es exactamente k, hemos terminado. Si esto es menor que k, entonces retrocedemos en la mitad superior de los primeros k elementos de A, y si esto es mayor que k retrocedemos en la mitad inferior de los primeros elementos de k, etc. Eventualmente, o bien Encuentra que el kth elemento más grande está en la matriz A, en cuyo caso hemos terminado. De lo contrario, repita este proceso en la matriz B.

El tiempo de ejecución de este algoritmo es el siguiente. La búsqueda de la matriz A realiza una búsqueda binaria sobre k elementos, que toma iteraciones O (lg k). Cada iteración cuesta O (lg n), ya que tenemos que hacer una búsqueda binaria en B. Esto significa que el tiempo total para esta búsqueda es O (lg k lg n). El tiempo para hacer esto en la matriz B es el mismo, por lo que el tiempo de ejecución neto para el algoritmo es O (lg k lg n) = O (lg ² n) = o (n), que es sublineal.

Answer 3

Esta es una respuesta bastante similar a la de Kirk.

Deje que Find( nth, A, B ) sea ​​una función que devuelva nth number, y | A | + | B | > = n. Este es un pseudo código simple sin verificar si uno de los arreglos es pequeño, menos de 3 elementos. En el caso de una matriz pequeña, una o dos búsquedas binarias en una matriz más grande son suficientes para encontrar el elemento necesario.

Find( nth, A, B )
  If A.last() <= B.first():
    return B[nth - A.size()]
  If B.last() <= A.first():
    return A[nth - B.size()]
  Let a and b indexes of middle elements of A and B
  Assume that A[a] <= B[b] (if not swap arrays)
  if nth <= a + b:
    return Find( nth, A, B.first_half(b) )
  return Find( nth - a, A.second_half(a), B )

Es log(|A|) + log(|B|) , y debido a que se pueden hacer matrices de entrada para tener n elementos, cada uno es de complejidad log(n) .

Answer 4

Creo que se trata de dos búsquedas binarias simultáneas en los subarreglos A[0..n-1] y B[0..n-1] , que es O (log n).

• Dados los arreglos ordenados, usted sabe que el nth más grande aparecerá en algún lugar antes o en A[n-1] si está en el arreglo A , o B[n-1] si está en el arreglo B
• Considere el ítem en el índice a en A y el ítem en el índice b en B
• Realice la búsqueda binaria de la siguiente manera (pseudocódigo bastante aproximado, sin tener en cuenta los problemas ''únicos''):
  • Si a + b > n , entonces reduce el conjunto de búsqueda
    • si A[a] > B[b] entonces b = b / 2 , sino a = a / 2
  • Si a + b < n , aumente el conjunto de búsqueda
    • si A[a] > B[b] entonces b = 3/2 * b , sino a = 3/2 * a (a medio camino entre a y la a anterior)
  • Si a + b = n , la enésima más grande es max(A[a], B[b])

Creo que el peor de los casos es O (ln n), pero en cualquier caso definitivamente sublineal.

Answer 5

int[] a = new int[] { 11, 9, 7, 5, 3 };
int[] b = new int[] { 12, 10, 8, 6, 4 };
int n = 7;
int result = 0;
if (n > (a.Length + b.Length))
    throw new Exception("n is greater than a.Length + b.Length");
else if (n < (a.Length + b.Length) / 2)
{
    int ai = 0;
    int bi = 0;
    for (int i = n; i > 0; i--)
    {
        // find the highest from a or b
        if (ai < a.Length)
        {
            if (bi < b.Length)
            {
                if (a[ai] > b[bi])
                {
                    result = a[ai];
                    ai++;
                }
                else
                {
                    result = b[bi];
                    bi++;
                }
            }
            else
            {
                result = a[ai];
                ai++;
            }
        }
        else
        {
            if (bi < b.Length)
            {
                result = b[bi];
                bi++;
            }
            else
            {
                // error, n is greater than a.Length + b.Length
            }
        }
    }
}
else
{
    // go in reverse
    int ai = a.Length - 1;
    int bi = b.Length - 1;
    for (int i = a.Length + b.Length - n; i >= 0; i--)
    {
        // find the lowset from a or b
        if (ai >= 0)
        {
            if (bi >= 0)
            {
                if (a[ai] < b[bi])
                {
                    result = a[ai];
                    ai--;
                }
                else
                {
                    result = b[bi];
                    bi--;
                }
            }
            else
            {
                result = a[ai];
                ai--;
            }
        }
        else
        {
            if (bi >= 0)
            {
                result = b[bi];
                bi--;
            }
            else
            {
                // error, n is greater than a.Length + b.Length
            }
        }
    }
}
Console.WriteLine("{0} th highest = {1}", n, result);