Dado un conjunto de números 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. No se permitió usar hash. La complejidad del algoritmo debe ser O (n)Dado un conjunto 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?
Supongo que la matriz no está ordenada, o similar, 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, entonces ese es el número que se repite 3 veces en una ejecución contigua.
Si las repeticiones están dispersas, entonces el problema se vuelve más interesante.
Dado que esto es tarea, solo le 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 un exclusivo-o de todos los números en 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.
Por ejemplo, 3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7.
Gracias polygenelubricants por su pista. Tengo que descubrir cómo diferenciar entre los números que se repiten una y tres veces. –
Me interesa saber exactamente cómo planea usar xor, ya que esta vez tiene más números que pueden aparecer un número impar de veces (algunos números pueden aparecer una sola vez, luego aparece el que aparece 3 veces). – IVlad
@stubbscroll: La pregunta está redactada como si fuera un problema de tarea. Es abstracto, pero inusualmente específico; se ajusta al patrón "Dada X, encuentra Y"; y exige "La complejidad del algoritmo debe ser O (n)". – Gabe
Bueno, todo lo que puedo pensar es esto, pero estoy seguro de que su profesor está buscando una ecuación difícil que lo resuelva en 1 escaneo. Puede hacerlo en 2 escaneos que es O (n), suponiendo que puede crear un 2º conjunto de tamaños (0 a número máximo en 1ra matriz). Escanee una vez, encuentre el número máximo en la matriz. Crea una segunda matriz de ese tamaño. Vuelva a iterar sobre la 1ra matriz usando la segunda matriz como cubetas para incrementar el conteo de cada elemento en la 1ra matriz. Una vez que incrementa un cubo a 3 esa es su solución. No es el mejor, pero funcionaría en algunos casos.
Si conoce min y max de la secuencia de enteros y min> = 0, cree una matriz [min, max] llena de ceros. Escanee el conjunto dado y, si lo hago, incremente la posición i-ésima en uno. Después de terminar, tiene la tabla de frecuencia en la segunda matriz, donde la posición de la matriz apunta a un número entero.
Si max - min >>> n, entonces esto no es O (n). – user287792
algoritmo: debería haber una opción de usar la matriz dispersa (http://en.wikipedia.org/wiki/Sparse_array), como lista vinculada. –
¿Cómo propone implementar una matriz dispersa con operaciones de tiempo constante sin hash? – user287792
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 mezcla de idiomas :-) También, esto es realmente estúpido tener una matriz que puede ser indexado con cualquier número entero - puede hacerlo en un sistema de 64 bits y lo hace cumplir con los requisitos.
¿Qué sucede si se trata de un lenguaje como Python o Scheme que permite números enteros de tamaño arbitrario? – Gabe
Esto funciona en teoría (suponiendo solo entradas de 32 bits), pero nunca (quizás, quizás no, NUNCA, pero entiendas el punto) vas a poder declarar una matriz de 4 294 967 296 entradas. – IVlad
-1: He oído hablar de espacio comercial por tiempo, ¡pero dulce Jesús! Un int de 32 bits = 4 bytes, por lo que una matriz int 2^32 es de aproximadamente 4 GB. La entrevista terminará muy rápido si alguien escribió un código como este. – Juliet
Use radix sort (que es lineal en el número de bits necesarios para especificar los enteros), luego escanee para buscar el triplete.
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();
}
Esto no es una instanciación de un algoritmo O (n). – user287792
Este algoritmo se ve bastante bueno .... pero no sé su implementación .. Sólo pseudocódigo .... Si ANY1 buena tratar sus manos en código (programación C), a continuación, por favor, publicarlo ....
PseudoCode va aquí ... Toma dos conjuntos de bitset 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 + 1º elemento.
para cada número entero 'i' if (array2 [i] == 1) array2 [i] = 0, array1 [i] = 1; else array2 [i] = 1;
para cada elemento K en las matrices si (array1 [k] & & array2 [k]) retorno k;
Complejidad = O (n) y Espacio = 2n bits.
Aquí es una respuesta que asume max (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;
}
En esencia, el problema consiste en calcular el modo de la matriz. Esta solución funciona "SOLAMENTE" si el rango de matriz es [0, n-1]. Poniendo la solución aquí ya que el problema no pone una cláusula del rango.
Esto es O (n) con O (1) espacio (pero con una cláusula de rango).
No conozco ningún algoritmo para calcular el modo en O (n), O (1) sin cláusulas en el rango.
También puede normalizar la entrada de la matriz a 0, n-1 y su solución será un poco más genérica para manejar las matrices con p, q rangos donde q = p <= n. – sharjeel
no veo de qué se trata todo el alboroto: usando python 2.6 y una función simple que va sobre la lista, cuenta las ocurrencias, 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
python tiene la ventaja de una matriz asociativa, que es similar a la ordenación por cubo o la ordenación por radix, como se sugiere en otras respuestas. se ejecuta en O (n) pero también usa espacio (n) – shak
@shak Estupendo, y estoy seguro de que también me dirá por qué agregó este comentario casi un año después de haber proporcionado esta respuesta. ¿Tal vez quieres agregar tu propia respuesta? ¿Tal vez quieres proporcionar un enlace a lo que acabas de mencionar? –
El algoritmo de Bugaoo se ve bien que se cita a continuación. En realidad, podemos generalizarlo haciendo un pase extra antes del "1er pase" para encontrar el mínimo (A) y máximo (A) y otro pase adicional para mover cada elemento en A al rango de min (A) y máximo (A) , es decir, A [0] - min (A). Después de "1st pass" y "2nd pass" (tenga en cuenta que debemos modificar los elementos por max (A) - min (A) en lugar de n), podríamos agregar min (A) al número duplicado encontrado finalmente.
Básicamente, 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. Suponga que 'n' es el tamaño de la matriz Escanee la matriz y marque A [A [i]] = A [A [i]] + n -----> 1er pase Divida cada elemento de la matriz entre 'n' , es decir, A [i] = A [i]/n ----> 2da pasada El elemento con el valor máximo desde la 2da pasada es la respuesta. Esto es O (n) con O (1) espacio (pero con una cláusula de rango). No conozco ningún algoritmo para calcular el modo en O (n), O (1) sin cláusulas en el rango.
http://stackoverflow.com/questions/555744/algorithm-to-find-two-repeated-numbers-in-an-array-without-sorting – AVB
@ Chris Dodd - Estoy un poco inclinado a estar de acuerdo Contigo, pero basado en lo publicado por los polileneocubridos, sospecho que hay una forma inteligente de hacerlo.No puedo resolverlo, pero estoy ansioso por descubrir cuál es la respuesta. –
@SS usando hash, ¿esto significa que no puede usar mapas/diccionarios o simplemente que no puede usar una función hash en cada número para resolverlo? –