C obtener modo de lista de enteros

Necesito escribir un progtwig para encontrar el modo. O la mayor ocurrencia de un entero o enteros. Asi que,

1,2,3,4,1,10,4,23,12,4,1 tendría modo de 1 y 4.

No estoy realmente seguro de qué tipo de algoritmo debo usar. Me cuesta mucho pensar en algo que funcione.

Estaba pensando en una tabla de frecuencias de algún tipo, tal vez donde podría ir a través de una matriz y luego crear una lista enlazada. Si el enlace no contiene ese valor, agréguelo al enlace, si lo hace, agregue 1 al valor.

Así que si tuviera lo mismo desde arriba. bucle a través de 1,2,3,4,1,10,4,23,12,4,1

Entonces la lista está vacía, así que agregue el nodo con el número = 1 y el valor = 1. 2 no existe, así que agregue el nodo con el número = 2 y el valor = 1 y así sucesivamente. Llegar al 1 y el 1 ya existe, por lo que valor = 2 ahora.

Tendría que recorrer la matriz y luego recorrer la lista enlazada cada vez para encontrar ese valor.

Una vez que termine, vaya a la lista vinculada y cree una nueva lista vinculada que contendrá los modos. Así que puse la cabeza en el primer elemento que es 1. Luego paso por la lista enlazada que contiene las ocurrencias y comparo los valores. Si las ocurrencias del nodo actual es> la más alta actual, entonces establezco la cabeza en este nodo. Si es = al más alto, entonces agrego el nodo a la lista de modos vinculados.

Una vez que termine, recorro la lista de modos e imprimo los valores.

No estoy seguro si esto funcionaría. ¿Alguien ve algo malo con esto? ¿Hay alguna forma más fácil de hacer esto? Estaba pensando en una tabla de hash también, pero no estoy realmente seguro de cómo hacerlo en C.

Gracias.

El algoritmo que tienes está bien para una tarea. Hay todo tipo de cosas que podría hacer para optimizar el código, tales como:

  • utilizar un árbol binario para la eficiencia,
  • use una matriz de conteos donde el índice es el número (asumiendo que el rango del número es limitado).

Pero creo que encontrarás que no son necesarios en este caso. Para la tarea, la intención es solo mostrar que entiendes cómo progtwigr, no que sabes todo tipo de trucos para exprimir la última onza de rendimiento. Su educador buscará mucho más por código legible y estructurado que por optimizaciones difíciles.

Voy a describir a continuación lo que haría. Obviamente, eres libre de usar mi consejo tanto o tan poco como desees, dependiendo de la satisfacción que desees obtener al hacerlo tú mismo. Proporcionaré solo pseudocódigo, que es mi práctica estándar para las preguntas de la tarea.

Comenzaría con una estructura que contiene un número, un conteo y el siguiente puntero (para su lista enlazada) y el puntero global al primero:

typedef struct sElement { int number; int count; struct sElement *next; } tElement; tElement first = NULL; 

Luego crea algunas funciones para crear y usar la lista:

 tElement *incrementElement (int number); tElement *getMaxCountElement (void); tElement *getNextMatching (tElement *ptr, int count); 

Esas funciones serán, respectivamente:

  • Incremente la cuenta para un elemento (o créela y establezca la cuenta en 1).
  • Escanea todos los elementos devolviendo el conteo máximo.
  • Obtenga el siguiente puntero de elemento que coincida con el recuento, comenzando en un punto determinado, o NULL si no hay más.

El pseudocódigo para cada uno:

 def incrementElement (number): # Find matching number in list or NULL. set ptr to first while ptr is not NULL: if ptr->number is equal to number: return ptr set ptr to ptr->next # If not found, add one at start with zero count. if ptr is NULL: set ptr to newly allocated element set ptr->number to number set ptr->count to 0 set ptr->next to first set first to ptr # Increment count. set ptr->count to ptr->count + 1 

 def getMaxCountElement (number): # List empty, no mode. if first is NULL: return NULL # Assume first element is mode to start with. set retptr to first # Process all other elements. set ptr to first->next while ptr is not NULL: # Save new mode if you find one. if ptr->count is greater than retptr->count: set retptr to ptr set ptr to ptr->next # Return actual mode element pointer. return retptr 

 def getNextMatching (ptr, number): # Process all elements. while ptr is not NULL: # If match on count, return it. if ptr->number is equal to number: return ptr set ptr to ptr->next # Went through whole list with no match, return NULL. return NULL 

Entonces su progtwig principal se convierte en:

 # Process all the numbers, adding to (or incrementing in) list . for each n in numbers to process: incrementElement (n) # Get the mode quantity, only look for modes if list was non-empty. maxElem = getMaxCountElement () if maxElem is not NULL: # Find the first one, whil exists, print and find the next one. ptr = getNextMatching (first, maxElem->count) while ptr is not NULL: print ptr->number ptr = getNextMatching (ptr->next, maxElem->count) 

Si puede mantener la lista completa de enteros en la memoria, puede ordenar la lista primero, lo que hará que los valores repetidos sean adyacentes entre sí. Luego puede hacer una sola pasada sobre la lista ordenada para buscar el modo. De esa manera, solo necesita realizar un seguimiento de los mejores candidatos para el modo visto hasta ahora, junto con la cantidad de veces que se ha visto el valor actual hasta el momento.

Si el rango de números se conoce de antemano y es un número razonable, puede asignar una matriz suficientemente grande para los contadores y simplemente count[i] += 1 .

Si el rango de números no se conoce de antemano, o es demasiado grande para el uso ingenuo de una matriz, en su lugar, podría mantener un árbol binario de valores para mantener sus contadores. Esto le dará mucha menos búsqueda que una lista enlazada. De cualquier manera, tendrías que atravesar la matriz o el árbol y construir un orden de conteos de mayor a menor. Una vez más, recomendaría un árbol para eso, pero la solución de la lista también podría funcionar.

Otra opción interesante podría ser el uso de una cola de prioridad para su fase de extracción. Una vez que haya completado su lista de contadores, recorra su árbol e inserte cada valor con una prioridad igual a su cuenta. Luego simplemente extrae los valores de la cola de prioridad hasta que el conteo disminuye.

Me gustaría una solución basada en tabla hash simple.

Una estructura para la tabla hash que contiene un número y la frecuencia correspondiente. Más un puntero al siguiente elemento para encadenar en el cubo de hash.

 struct ItemFreq { struct ItemFreq * next_; int number_; int frequency_; }; 

El procesamiento comienza con

 max_freq_so_far = 0; 

Recorre la lista de números. Para cada number , la tabla hash se busca para un elemento ItemFreq x tal que x.number_ == number .

  • Si no se encuentra tal x , entonces un elemento ItemFreq se crea como { number_ = number, frequency_ = 1} y se inserta en la tabla hash.
  • Si se encontró alguna x entonces su frequency_ se incrementa.
  • Si frequency_ > max_freq_so_far entonces max_freq_so_far = frequency

Una vez que recorramos la lista de números completos, atravesamos la tabla hash e imprimimos los elementos ItemFreq cuya frequency_ == max_freq_so_far

La complejidad del algoritmo es O(N) donde N es el número de elementos en la lista de entrada.

Para una construcción simple y elegante de tabla hash, consulte la sección 6.6 de K&R (El lenguaje de progtwigción C) .

Esta respuesta es una muestra de la idea de Paul Kuliniewicz:

 int CompInt(const void* ptr1, const void* ptr2) { const int a = *(int*)ptr1; const int b = *(int*)ptr2; if (a < b) return -1; if (a > b) return +1; return 0; } // This function leave the modes in output and return the number // of modes in output. The output pointer should be available to // hold at least n integers. int GetModes(const int* v, int n, int* output) { // Sort the data and initialize the best result. qsort(v, v + n, CompInt); int outputSize = 0; // Loop through elements while there are not exhausted. // (look there is no ++i after each iteration). for (int i = 0; i < n;) { // This is the begin of the new group. const int begin = i; // Move the pointer until there are no more equal elements. for (; i < n && v[i] == v[begin]; ++i); // This is one-past the last element in the current group. const int end = i; // Update the best mode found until now. if (end - begin > best) { best = end - begin; outputSize = 0; } if (end - begin == best) output[outputSize++] = v[begin]; } return outputSize; }