arrays - unidimensionales - ejercicios resueltos de arreglos en c++ pdf

Algoritmo para encontrar k números más pequeños en una matriz de n artículos

Question

Estoy tratando de escribir un algoritmo que pueda imprimir los k números más pequeños en una matriz de tamaño n en O (n), pero no puedo reducir la complejidad del tiempo a n. ¿Cómo puedo hacer esto?

Answer 1

¿Qué hay de usar un montón para almacenar los valores. Este costo es n cuando pasa por cada valor en la matriz.

Luego recorra el montón para obtener los valores k más pequeños.

El tiempo de ejecución es O (n) + O (k) = O (n)

Por supuesto, el espacio de memoria ahora es O (n + n)

Answer 2

Como se mencionó, hay dos maneras de realizar dicha tarea:

1) Puede ordenar toda la matriz de n elementos con el algoritmo de ordenación de ordenación quicksort , heapsort o O (n log n) que desee, y luego seleccionar los m valores más pequeños en su matriz. Este método funcionará en O(n log n) .

2) Puede usar un http://en.wikipedia.org/wiki/Selection_algorithm para encontrar m elementos más pequeños en su matriz. Tomará O(n) tiempo encontrar el valor más pequeño kth , ya que repetirá este algoritmo m veces, el tiempo total será mx O(n) = O(n) .

Answer 3

Es posible encontrar los k más pequeños de n elementos en el tiempo O(n) (por lo que quiero decir el tiempo verdadero O(n) , no O(n + some function of k) ). Consulte http://en.wikipedia.org/wiki/Selection_algorithm , especialmente las subsecciones sobre "clasificación parcial desordenada" y "selección de la mediana como estrategia pivote", y también el artículo "Mediana de medianas" para la pieza esencial que hace que esta O(n) .

Answer 4

Esto se puede hacer en el tiempo lineal esperado (O (n)). Primero encuentre el kth elemento más pequeño de la matriz (usando el método de partición dinámica para encontrar el estadístico de orden kth ) y luego simplemente itere a través del bucle para verificar qué elementos son menores que el kth elemento más pequeño. Tenga en cuenta que esto funciona correctamente solo para distintos elementos.

Aquí está el código en c:

    /*find the k smallest elements of an array in O(n) time. Using the Kth order 
statistic-random pivoting algorithm to find the kth smallest element and then looping 
through the array to find the elements smaller than kth smallest element.Assuming 
distinct elements*/


    #include <stdio.h>
    #include <math.h>
    #include <time.h>
    #define SIZE 10
    #define swap(X,Y) {int temp=X; X=Y; Y=temp;}


    int partition(int array[], int start, int end)
    {
        if(start==end)
            return start;
        if(start>end)
            return -1;
        int pos=end+1,j;
        for(j=start+1;j<=end;j++)
        {       
            if(array[j]<=array[start] && pos!=end+1)
            {
                swap(array[j],array[pos]);
                pos++;
            }
            else if(pos==end+1 && array[j]>array[start])
                pos=j;
        }
        pos--;
        swap(array[start], array[pos]);
        return pos;
    }

    int order_statistic(int array[], int start, int end, int k)
    {
        if(start>end || (end-start+1)<k)
            return -1;                   //return -1 
        int pivot=rand()%(end-start+1)+start, position, p;
        swap(array[pivot], array[start]);
        position=partition(array, start, end);
        p=position;
        position=position-start+1;                  //size of left partition
        if(k==position)
            return array[p];
        else if(k<position)
            return order_statistic(array, start,p-1,k);
        else
            return order_statistic(array,p+1,end,k-position);
    }


    void main()
    {
        srand((unsigned int)time(NULL));
        int i, array[SIZE],k;
        printf("Printing the array.../n");
        for(i=0;i<SIZE;i++)
            array[i]=abs(rand()%100), printf("%d ",array[i]);
        printf("/n/nk=");
        scanf("%d",&k);
        int k_small=order_statistic(array,0,SIZE-1,k);
        printf("/n/n");
        if(k_small==-1)
        {
            printf("Not possible/n");
            return ;
        }
        printf("/nk smallest elements.../n");
        for(i=0;i<SIZE;i++)
        {
            if(array[i]<=k_small)
                printf("%d ",array[i]);
        }
    }

Answer 5

He hecho esto en una entrevista antes, y una de las formas más elegantes y eficientes de hacerlo es

O(n log k). 
with space: O(k) (thanks, @Nzbuu)

Básicamente, vas a utilizar un tamaño máximo de k limitado a k. Para cada elemento de la matriz, verifique si es más pequeño que el máximo (solo O (1)). Si es así, coloque eso en el montón (O (log k)) y elimine el máximo. Si es más grande, ve al siguiente artículo.

Por supuesto, el montón no produce una lista ordenada de k elementos, pero eso se puede hacer en O (k log k), que es fácil.

De manera similar, puedes hacer lo mismo para encontrar los elementos k más grandes, en cuyo caso usarías un montón mínimo.

Answer 6

La mejor solución posible para el problema es la siguiente. Use Ordenación rápida para encontrar pivotes y deseche la parte donde no se encuentra este elemento kth, y recursivamente busque el próximo pivote. (Es el kth Max finder. Debes cambiar la condición "if" para que sea kth Min Finder). Aquí está el código de JavaScript .

  // Complexity is O(n log(n))
  var source = [9, 2, 7, 11, 1, 3, 14, 22];

  var kthMax = function(minInd, MaxInd, kth) {
      // pivotInd stores the pivot position 
      // for current iteration
      var temp, pivotInd = minInd;
      if (minInd >= MaxInd) {
        return source[pivotInd];
      }

      for (var i = minInd; i < MaxInd; i++) {
        //If an element is greater than chosen pivot (i.e. last element)
        //Swap it with pivotPointer element. then increase ponter
        if (source[i] > source[MaxInd]) {
          temp = source[i];
          source[i] = source[pivotInd];
          source[pivotInd] = temp;
          pivotInd++;
        }
      }
      // we have found position for pivot elem. 
      // swap it to that position place .
      temp = source[pivotInd];
      source[pivotInd] = source[MaxInd];
      source[MaxInd] = temp;

      // Only try to sort the part in which kth index lies.
      if (kth > pivotInd) {
        return kthMax(pivotInd + 1, MaxInd, kth);
      } else if (kth < pivotInd) {
        return kthMax(minInd, pivotInd - 1, kth);
      } else {
        return source[pivotInd];
      }

    }
    // last argument is kth-1 , so if give 2 it will give you,
    // 3rd max which is 11

  console.log(kthMax(0, source.length - 1, 2));

Answer 7

No sé exactamente lo que está buscando, sino el tiempo O (n * k) y el espacio O (k) bastante simples. Este es el K más grande, así que necesitarías tirarlo.

Para el bruto por min de k (resultado) puede sustituir un montón

private int[] FindKBiggestNumbersM(int[] testArray, int k)
{
    int[] result = new int[k];
    int indexMin = 0;
    result[indexMin] = testArray[0];
    int min = result[indexMin];

    for (int i = 1; i < testArray.Length; i++)
    {
        if(i < k)
        {
            result[i] = testArray[i];
            if (result[i] < min)
            {
                min = result[i];
                indexMin = i;
            }
        }
        else if (testArray[i] > min)
        {
            result[indexMin] = testArray[i];
            min = result[indexMin];
            for (int r = 0; r < k; r++)
            {
                if (result[r] < min)
                {
                    min = result[r];
                    indexMin = r;
                }
            }
        }
    }
    return result;
}

Answer 8

Otra técnica: use el algoritmo de selección rápida y el resultado serían todos los elementos a la izquierda del resultado devuelto. El tiempo promedio de complejidad sería O (n) y, en el peor de los casos, sería O (n ^ 2). La complejidad del espacio sería O (1).

Answer 9

Simplemente ordene la matriz con Merge Sort y luego imprima el primer número k, tomará n * log2 (n) en el peor de los casos.

Answer 10

Suponiendo que está intentando mostrar los números más pequeños de K, puede usar el algoritmo de selección de Hoare para encontrar el ^número más pequeño de k. Eso divide la matriz en los números más pequeños, el número k ^th y los números más grandes.

Answer 11

Tendrá que encontrar el elemento k''th más pequeño usando ''algoritmo de selección'', que es O (n), y luego iterar nuevamente la matriz y devolver cada elemento que sea más pequeño / igual.
algoritmo de selección: http://en.wikipedia.org/wiki/Selection_algorithm
tendrá que prestar atención si tiene repeticiones: deberá asegurarse de que no está devolviendo más de k elementos (es posible si, por ejemplo, tiene 1,2, ..., k, k, k, ... .)

EDITAR:
el algoritmo completo, y devolver una lista, según lo solicitado: deje que la matriz sea A

 1. find the k''th element in A using ''selection algorithm'', let it be ''z''
 2. initialize an empty list ''L''
 3. initialize counter<-0
 4. for each element in A: 
 4.1. if element < z: 
   4.1.1. counter<-counter + 1 ; L.add(element)
 5. for each element in A:
 5.1. if element == z AND count < k:
   5.1.1. counter<-counter + 1 ; L.add(element)
 6. return L

tenga en cuenta que se requiere una tercera iteración si su lista puede tener duplicados. si no puede, es innecesario, simplemente cambie la condición en 4.1 a <=.
también tenga en cuenta: L.add está insertando un elemento en una lista vinculada y, por lo tanto, es O (1).