Encuentre el elemento que ocurre b veces en una una matriz de tamaño n * k + b

Question

Descripción

Dada una matriz de tamaño (n*k+b) donde n elementos se producen k veces y un elemento se produce B veces, en otras palabras, hay son n+1 Elementos distintos. Dado que 0 < b < k encuentra el elemento que ocurre b veces.

Mis soluciones intentadas

1. solución obvia van a utilizar hash, pero no va a funcionar si los números son muy grandes. La complejidad es O(n)

2. Usando mapa para almacenar las frecuencias de cada elemento y después de atravesar un mapa para encontrar el elemento que ocurre b times.As Mapa de se implementan como árboles de altura equilibrada complejidad será O(nlogn).

Ambos de mi solución fueron aceptadas pero el entrevistador quería una solución lineal sin utilizar hash y la pista que dio fue hacer que la altura de la constante de árbol en árbol en el que va a almacenar frecuencias, pero no soy capaz de figura la solución correcta todavía.

Quiero saber cómo resolver este problema en tiempo lineal sin hash?

EDIT:

muestra:

de entrada: n=2 b=2 k=3

aMatriz: 2 2 2 3 3 3 1 1

de salida: 1

Answer 1

Un idea usando grupos cíclicos

Para adivinar el i-ésimo bit de respuesta, siga este procedimiento:

1. contar cuántos números de matriz tiene establecido el bit i-ésimo, tienda como cnt
2. cnt % k Si no es cero, entonces i-ésimo bit de respuesta está configurado. De lo contrario, está claro.

Para adivinar el número entero, repita lo anterior para cada bit.

Esta solución es técnicamente O((n*k+b)*log max N), donde max N es el valor máximo en la tabla, pero como el número de bits suele ser constante, esta solución es lineal en tamaño de matriz.

Sin hash, el uso de memoria es O(log k * log max N).

ejemplo de implementación:

from random import randint, shuffle 

def generate_test_data(n, k, b): 
    k_rep = [randint(0, 1000) for i in xrange(n)] 
    b_rep = [randint(0, 1000)] 
    numbers = k_rep*k + b_rep*b 
    shuffle(numbers) 
    print "k_rep: ", k_rep 
    print "b_rep: ", b_rep 
    return numbers 

def solve(data, k): 
    cnts = [0]*10 
    for number in data: 
     bits = [number >> b & 1 for b in xrange(10)] 
     cnts = [cnts[i] + bits[i] for i in xrange(10)] 
    return reduce(lambda a,b:2*a+(b%k>0), reversed(cnts), 0) 

print "Answer: ", solve(generate_test_data(10, 15, 13), 3) 

Answer 2

el fin de tener una altura constante B-árbol que contiene n elementos distintos, con altura h constante, necesita z=n^(1/h) niños por nodos: h=log_z(n), por lo tanto h=log(n)/log(z), por lo tanto log(z)=log(n)/h, por lo tanto z=e^(log(n)/h), por lo z=n^(1/h).

Ejemplo, con n=1000000, h=10, z=3.98, es decir z=4.

El tiempo para llegar a un nodo en ese caso es O(h.log(z)). Suponiendo h y z sea "constante" (ya que N=n.k, entonces log(z)=log(n^(1/h))=log(N/k^(1/h))=ct eligiendo adecuadamente h basado en k, a continuación, puede decirse que O(h.log(z))=O(1) ... Esto es un poco exagerado, pero tal vez ese era el tipo de cosas que el entrevistador ? quería oír

Answer 3

asumo:

1. los elementos de la matriz son comparables
2. conocemos los valores de n y k de antemano
3. Una solución de O (n * k + b..) es goo suficiente.

Supongamos que el número que se produce solo b veces es S. Estamos intentando encontrar el S en una matriz de tamaño n * k + b.

Recursive Paso: Encuentra el elemento mediano de la porción de la matriz actual como en la clasificación rápida en el tiempo del lineador. Deje que el elemento mediano sea M.

Después del paso recursivo, tiene una matriz donde todos los elementos menores que M aparecen a la izquierda de la primera ocurrencia de M. Todos los elementos M están uno al lado del otro y todos los elementos son mayores que M están a la derecha de todas las ocurrencias de M.

Mire el índice de la M más a la izquierda y calcule si S < M o S > = M. Recurse en el sector izquierdo o en el sector derecho.

Así que estás haciendo una clasificación rápida pero explorando solo una parte de las divisiones en cualquier momento. Recurrirá O (logN) veces pero cada vez con 1/2, 1/4, 1/8, .. tamaños de la matriz original, por lo que el tiempo total seguirá siendo O (n).

Aclaración: Digamos que n = 20 y k = 10. Entonces, hay 21 elementos distintos de la matriz, 20 de los cuales se producen 10 veces y el último se producen digamos 7 veces. Encuentro el elemento medio, digamos que es 1111. Si el S < 1111 que el índice de la ocurrencia más a la izquierda de 1111 será menor que 11 * 10. Si S> = 1111, entonces el índice será igual a 11 * 10.

Ejemplo completo: n = 4. k = 3. Matriz = {1,2,3,4,5,1,2,3,4,5,1,2,3,5} Después el primer paso recursivo encuentro que el elemento mediano es 3 y la matriz es algo así como: {1,2,1,2,1,2,3,3,3,5,4,5,5,4} Hay 6 los elementos a la izquierda de 3. 6 es un múltiplo de k = 3. Entonces cada elemento debe estar ocurriendo 3 veces allí. Entonces S> = 3. Recurse en el lado derecho. Y así.

Answer 4

ACTUALIZACIÓN: éste utilización de hash, así que no es una buena respuesta :(

en Python esto sería un tiempo lineal (set eliminará los duplicados):

result = (sum(set(arr))*k - sum(arr))/(k - b) 

Answer 5

Si 'k' es par y 'b' es impar, entonces XOR hará. :)