algorithm - saber - leer 10 números enteros almacenarlos en un arreglo y determinar cuántas veces está repetido el mayor

Dada una matriz de enteros donde algunos números se repiten 1 vez o 2 veces pero un número se repite 3 veces, ¿cómo lo encuentras?

Question

Dada una matriz de enteros donde algunos números se repiten 1 vez, algunos números se repiten 2 veces y solo un número se repite 3 veces, ¿cómo se encuentra el número que se repite 3 veces? El uso de hash no estaba permitido. La complejidad del algoritmo debe ser O (n)

Answer 1

Aquí hay una respuesta que asume que el máximo (A) es razonablemente pequeño, donde A es la matriz de entrada:

int ValidCount(int[] a, int[] b, int i, int n) {
  int num = a[i];
  int ret = 0;
  if (b[3*num] >= 0 && b[3*num] < n && a[b[3*num]] == num) ret++;
  if (b[3*num+1] >= 0 && b[3*num+1] < n && a[b[3*num+1]] == num) ret++;
  if (b[3*num+1] >= 0 && b[3*num+2] < n && a[b[3*num+2]] == num) ret++;
  b[3*num+ret] = i;
  return ++ret;
}

int threerep(int[] A, int aSize) {
  int *B = malloc(sizeof(int) * 3 * max(A, aSize)); /* Problematic if max(A) is large */
  /* Note that we don''t rely on B being initialized before use */
  for(int i = 0; i < aSize; i++) {
    if (ValidCount(A, B, i, aSize) == 3) return A[i];
  }
  return ERROR_NO_ANSWER;
}

Answer 2

Bueno, todo lo que puedo pensar es esto, pero estoy seguro de que su profesor está buscando una ecuación complicada que resuelva esto en 1 escaneo. Puede hacerlo en 2 exploraciones, que es O (n), suponiendo que puede crear una segunda matriz de tamaño (de 0 a número máximo en la primera matriz). Escanear una vez, encontrar el número máximo en la matriz. Crea 2da matriz de ese tamaño. Iterar sobre la 1ra matriz nuevamente usando la 2da matriz como grupos para incrementar el conteo de cada elemento en la 1ra matriz. Una vez que incrementas un cubo a 3 esa es tu solución. No es el mejor pero funcionaría en algunos casos.

Answer 3

El algoritmo de Bugaoo se ve bien que se cita a continuación. En realidad, podemos generalizarlo haciendo una pasada extra antes de "1st pass" para encontrar min (A) y max (A) y otra pasada adicional para mover cada elemento en A al rango de min (A) y max (A) , es decir, A [0] -min (A). Después de "1st pass" y "2nd pass" (tenga en cuenta que deberíamos modificar los elementos en max (A) -min (A) en lugar de n), podríamos agregar min (A) al número duplicado que se encuentra al final.

Esencialmente, el problema es calcular el modo de la matriz. Esta solución funciona "SOLAMENTE" si el rango de la matriz es [0, n-1]. Poniendo la solución aquí ya que el problema no pone una cláusula del rango. Supongamos que ''n'' es el tamaño del arrayScan el array y marque A [A [i]] = A [A [i]] + n -----> 1st pass Divide cada elemento del array por ''n'', es decir A [i] = A [i] / n ----> 2nd pass El elemento con el valor máximo del 2nd pass es la respuesta. Esto es O (n) con O (1) espacio (pero con una cláusula de rango). No tengo conocimiento de ningún algoritmo para calcular el modo en O (n), O (1) sin cláusulas en el rango.

Answer 4

Esencialmente, el problema es calcular el modo de la matriz. Esta solución funciona "SOLAMENTE" si el rango de la matriz es [0, n-1] . Poniendo la solución aquí ya que el problema no pone una cláusula del rango.

• Supongamos que ''n'' es el tamaño de la matriz
• Escanee la matriz y marque A [A [i]] = A [A [i]] + n -----> 1a pasada
• Divide cada elemento del arreglo por ''n'', es decir, A [i] = A [i] / n ----> 2da pasada
• El elemento con el valor máximo de la segunda pasada es la respuesta.

Esto es O (n) con O (1) espacio (pero con una cláusula de rango).

No tengo conocimiento de ningún algoritmo para calcular el modo en O (n), O (1) sin cláusulas en el rango.

Answer 5

Este algoritmo se ve bastante bueno ... pero no sé su implementación ... Sólo pseudocódigo ... Si alguno de ellos bien, prueba el código (programación en C), por favor publícalo ...

PseudoCode va aquí ... Tome dos arreglos de conjuntos de bits de tamaño n. Podemos usar esta matriz para contar hasta tres ocurrencias, es decir, si array1 [i] = 1 y array2 [i] = 1, entonces significa que tenemos tres ocurrencias de i + 1th elemento.

para cada entero ''i'' si (array2 [i] == 1) array2 [i] = 0, array1 [i] = 1; si no array2 [i] = 1;

para cada elemento K en las matrices si (array1 [k] && array2 [k]) devuelve k;

Complejidad = O (n) y Espacio = 2n bits.

Answer 6

No veo de qué se trata todo este alboroto: usar Python 2.6 y una función simple que recorre la lista, contabiliza las apariencias, una vez que encuentra un número que aparece 3 veces, lo devuelve.

>>> def find3(l):
    from collections import defaultdict
    d = defaultdict(int)
    for n in l:
        d[n]+=1
        if d[n] == 3:
            return n


>>> print find3([1,1,1,2,3,4,5,6,7])
1
>>> print find3([1,1,2,3,4,5,6,7,5])
None
>>> print find3([1,1,2,3,4,5,6,7,5,4,5,5])
5

Answer 7

Presentaré una solución que funciona en general en general, de manera que un número aparece m veces y otras n veces.

Necesitamos un operador que cancele n ocurrencias de un entero, pero mantiene m ocurrencias. Si convertimos cada número a su representación binaria, y para cada posición de bit, contamos el número de veces que se establece este bit, el valor será un múltiplo de n para todos los números que ocurren n veces, más 0 o m para el correspondiente bit del entero solitario.

Si luego tomamos el módulo n de cada uno de estos conteos, y dividimos por m , el resultado es el valor de la posición del bit correspondiente para el entero único. Todo lo que queda es convertir el resultado binario a decimal formal.

For example, given array = [3, -4, 3, 3], m = 1 and n = 3:
Binary of 3 = 011
Binary of -4 (2s complement) = 11111111111111111111111111111100

Bit 0: 3 % 3 = 0
Bit 1: 3 % 3 = 0
Bit 2 through 32: 1 % 3 = 1
The result is -4

Answer 8

Si conoce min y max de la secuencia de enteros y min> = 0, cree una matriz [min, max] rellena con ceros. Escanee la matriz dada y si ocurre, incremente la posición i-th en uno. Después de terminar, tiene la tabla de frecuencias en la segunda matriz, donde la posición de la matriz apunta a un entero.

Answer 9

Supongo que la matriz no está ordenada, o similarmente, las repeticiones de un número no aparecen en una ejecución contigua. De lo contrario, el problema es realmente trivial: simplemente escanee la matriz una vez con una ventana de tamaño 3, y si cada número en esa ventana es el mismo, ese es el número que se repite 3 veces en una ejecución contigua.

Si las repeticiones se dispersan, entonces el problema se vuelve más interesante.

Ya que esto es tarea, solo te daré una pista.

Este problema es un primo de donde se le da una matriz de enteros sin clasificar, y todos los números aparecen un número par de veces, excepto uno que aparece un número impar de veces.

Ese número se puede encontrar fácilmente en O(N) realizando una exclusiva o de todos los números de la matriz; el resultado es el número que aparece un número impar de veces.

La razón por la que esto funciona es que x xor x = 0 .

Entonces, por ejemplo, 3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7 .

Answer 10

Utilice la ordenación de radix (que es lineal en el número de bits necesarios para especificar los enteros), luego busque el triplete.

Answer 11

void main()
{
    int a[10]={1,5,2,8,5,9,0,5,3,7}, n, i, j, k=0;
    int p;
    printf("/n");
    for(i=0; i<10; i++)
    {
        p=1;
        for(j=i+1; j<10; j++)
        {
            if(a[i]==a[j])
                p++;
        }
        if(p==3)
        {
            printf("the no is: %d",a[i]);
            getch();
            exit(0);
        }
    }
    printf("not available/n");
    getch();
}

Answer 12

int count[2^32]; for x in input: count[x] = 0; // delete this loop if you can assume ram is cleared to 0. for x in input: count[x]++; for x in input: if count[x] == 3: return x

Por favor, disculpe la combinación de idiomas :-) Además, esto es realmente estúpido tener una matriz que se puede indexar con cualquier número entero. Puede hacerlo en un sistema de 64 bits y cumple con los requisitos.