La entrada es una matriz que tiene como máximo un elemento que aparece al menos el 60% de las veces. El objetivo es encontrar si esta matriz tiene dicho elemento y, en caso afirmativo, encontrar ese elemento. Se me ocurrió una función de divide y vencerás que encuentra ese elemento.
from collections import Counter
def CommonElement(a):
c = Counter(a)
return c.most_common(1) #Returns the element and it's frequency
def func(array):
if len(array) == 1:
return array[0]
mid = len(array)//2
left_element = func(array[:mid])
right_element = func(array[mid:])
if left_element == right_element:
return right_element
most_common_element = CommonElement(array)
element_count = most_common_element[0][1] #Getting the frequency of the element
percent = element_count/len(array)
if percent >= .6:
return most_common_element[0][0] #Returning the value of the element
else:
return None
array = [10,9,10,10,5,10,10,10,12,42,10,10,44,10,23,10] #Correctly Returns 10
array = [10,9,10,8,5,10,10,10,12,42,10,12,44,10,23,5] #Correctly Returns None
result = func(array)
print(result)
Esta función funciona pero está en O(n log(n)). Quiero implementar un algoritmo que sea O(n)
La función de recursividad de mi algoritmo es T(n) = 2T(n/2) + O(n). Creo que el objetivo es eliminar la necesidad de encontrar la frecuencia, lo que requiere O(n). ¿Alguna idea?
Yo crearía un histogramo. Cree un diccionario donde la clave sea su número y el valor sea el número de entradas. Luego puedes escanear ese diccionario para ver si algún elemento tiene más del 60 % de las entradas.
- Tim Roberts
28 de marzo de 2021 a las 3:55
1
La partición/selección es O(n). Se garantiza que algo como una introselección para calcular la mediana producirá la respuesta correcta porque en la matriz ordenada, el número correcto ocupa el 60% del intervalo
- Físico loco
28 de marzo de 2021 a las 4:47
>p>
"La entrada es una matriz que tiene como máximo un elemento que aparece al menos el 60% de las veces." - bueno, no es que haya lugar para que dos elementos aparezcan con tanta frecuencia.
Usuario2357112
28 de marzo de 2021 a las 5:24
Pero hay espacio para que 0 elementos aparezcan al menos en un 60%. Lo que quise decir es que la matriz PODRÍA tener tal elemento. Pero es posible que tal elemento no exista.
& ndash; CrazyCSGuy
28 de marzo de 2021 a las 5:29
Parece que toda la parte de divide y vencerás de tu algoritmo no está haciendo nada por ti; podrías eliminarla por completo y obtendrías la respuesta de ggorlen.
Usuario2357112
28 de marzo de 2021 a las 5:40
------------------------------------
Si se garantiza que tendrá una lista en la que el 60 % es un número determinado, se garantiza que ese número será la mediana. Para ver esto intuitivamente, ordene la lista. El número en cuestión representaenvía una ventana contigua que tiene el 60% de la longitud de la lista. No hay forma de colocar esa ventana de manera que no cubra el medio.
Hay muchos algoritmos de divide y vencerás para encontrar la mediana. Uno común se llama introselección. Puede encontrar una implementación en las funciones de partición y argpartition de numpy (está escrita en C). La idea básica es realizar una clasificación rápida, pero solo recurrir a la parte que contiene el índice que le interesa. Esto reduce el algoritmo a O(n).
Por cierto, puedes buscar cualquier índice entre el 40% y el 60% de la longitud de la lista. El 50% parece un término medio razonable.
Para verificar que la mediana aparece > El 60 % de las veces, ejecute un único bucle sobre la matriz y cuente el número de veces que aparece la mediana.
2
Gracias por la información. Ni siquiera pensé en que el elemento fuera mediano. Necesito encontrar la mediana de la matriz en O(n) y verificar que ocurra al menos el 60% en O(n).
-CrazyCSGuy
28 de marzo de 2021 a las 5:32
@CrazyCSGuy. Verificar es fácil. Simplemente haga una sola pasada y cuente el número de ocurrencias.
- Físico loco
28 de marzo de 2021 a las 5:33
------------------------------------
Puedes crear un contador de frecuencia para todos los elementos de la lista una vez en O(n). Luego, repita la tabla de búsqueda y vea si alguno representa al menos el 60 % de los elementos (en otras palabras, count / len(lst) >= 0,6).
>>> from collections import Counter
>>> L = [4, 2, 3, 2, 4, 4, 4]
>>> Counter(L)
Counter({4: 4, 2: 1, 3: 1})
>>> Counter(L).most_common(1)
[(4, 4)]
>>> item, count = Counter(L).most_common(1)[0]
>>> count / len(L)
0.6666666666666666
>>> count / len(L) >= 0.6
True
Dividir y dividir conquistar es un enfoque creativo, pero inapropiado, para este problema.
...o eso pensaba, pero mira esta respuesta.
7
De hecho, si los hay, sería el que tenga el recuento más alto, por lo que bastaría con comprobar si supera el 60%.
Jurez
28 de marzo de 2021 a las 4:01
En realidad, esta es una tarea escolar que forma parte de la lección Divide y vencerás. Entonces, aunque me gustaría depender completamente de Counter, necesito implementar mi propio algoritmo Divide y vencerás.
-CrazyCSGuy
28 de marzo de 2021 a las 4:08
Interesante. No veo una manera de hacerlo mejor que O(n). O(log(n)) es imposible. ¿Tu tarea escolar o tu profesor te están diciendo que es posible resolver esto con D&C en O(n)?
- ggorlen
28 de marzo de 2021 a las 4:10
No estoy buscando que se resuelva en O(log n). Encontré una solución en O(n log n) pero no puedo pensar en una manera de hacerlo en O(n), así que quería preguntarle a "Internet". Voy a comprenderComuníquese con mi profesor si es posible, pero creo que debería serlo porque la pregunta es "implementar en O(n)", no "¿Puedes implementar en O(n)?".
-CrazyCSGuy
28 de marzo de 2021 a las 4:24
1
Acabo de hacerlo. Estoy en un dispositivo móvil, por lo que no hay una implementación de muestra. Puedes resolverlo si sabes cómo escribir clasificación rápida o si buscas Wikipedia o una fuente numerosa.
- Físico loco
28 de marzo de 2021 a las 5:11
------------------------------------
Existe un algoritmo bastante simple para encontrar el elemento mayoritario de una colección, si la colección lo tiene:
def majority(l):
count, candidate = 0, None
for element in l:
if count == 0:
count, candidate = 1, element
elif element == candidate:
count += 1
else:
count -= 1
return candidate
Este algoritmo esencialmente empareja cada elemento de la entrada con otro elemento con un valor diferente hasta que todos los elementos no emparejados tienen el mismo valor y luego devuelve ese valor. Si la entrada tiene un elemento mayoritario, el algoritmo debe devolverlo.
Puede calcular un candidato con este algoritmo, luego hacer otra pasada a través de la entrada y ver si ese candidato tiene una supermayoría del 60%. Esto funciona en espacio O(1) y tiempo O(n) sin mutar la entrada, mientras que los algoritmos basados en hash o basados en introselección necesitarían más espacio o mutar la entrada. También es inmune a los ataques de colisión de hash (a diferencia de Counter y otros hash-basenfoques ed) y no requiere que los elementos tengan una relación de orden (a diferencia de introselect).
