Dividir y conquistar - Array plural

Quiero diseñar un algoritmo que determine si un conjunto A es plural y devolver ese elemento.Dividir y conquistar - Array plural

Una matriz es plural cuando existe un elemento x en la matriz si más de la mitad de la matriz es igual a x.

Me pregunto si existe un algoritmo de división y conquista más eficiente que funciona mejor que el actual que tengo ahora.

Assume you have the array 

aaabbcac

dividiré recursivamente la matriz hasta que obtenga subarreglos de tamaño 2, de la siguiente manera.

aa ab bc ac

de aquí, voy a comparar cada elemento del subconjunto para ver si son iguales: Si es igual, el retorno del elemento, si no, regrese falsa.

aa ab bc ac 
a f f f

así que ahora tengo una matriz del elemento A y 3 falso.

yo estaba pensando en la combinación de ellos, así:

a f f f 
    a  f <----- combining a and f will give a 
    a <----- returns a

Pero, si nos fijamos en la matriz, tenemos 4 Atléticos, que no cumple los criterios de un conjunto plural. Debería devolver falso, si la matriz no fuera una matriz plural.

Creo que mi algoritmo se ejecutará en O (n lgn), debería ser un algoritmo correcto, que desafortunadamente no lo es.

¿Alguien puede indicarme la dirección correcta para esto?

Fuente

2011-03-01 ali

¿Tiene que ser un enfoque de dividir y conquistar? – gusbro

Sí Estoy buscando un algoritmo de dividir y conquistar. – ali

¿Es esta tarea? Estuviste muy cerca ... –

Esto es un problema de contar el número de ocurrencias de x. Divida la matriz en matrices secundarias y envíe el x junto con las matrices secundarias. Devuelve recuento, suma cuenta y comprueba si es mayor que el tamaño de la matriz.

Fuente

2011-03-01 15:04:38

¿a qué te refieres con enviar el x junto con sub arrays? – ali

En lugar de enviar matrices secundarias como 'aa ab bc ac' enviar tupples de sub array y el elemento' (aa, a), (ab, a), (bc, a), (ac, a) ' –

ah veo . entonces eso significa que la x que estoy enviando con las matrices secundarias será un elemento aleatorio, o será el elemento que está en la subcadena, en este ejemplo, aa – ali

También puede ordenar la matriz por algún algoritmo de clasificación (como quicksort), después de ese ciclo hasta (N + 1)/2 elemento verificando si n + 1 elemento es igual a n. Al usar quicksort tal enfoque sería con complejidad O(n*log n + n/2). Así que, básicamente, mi algoritmo estará limitado por la velocidad de clasificación.

Fuente

2011-03-01 15:42:59

Ah, ya veo ... pero supongo que solo puedo comparar los elementos de la matriz en función de la igualdad. Es decir, no puedo determinar si los elementos son menores o más que unos a otros. Además, ¿sería posible que el algo sea un tipo de división y conquista? – ali

Ok. Parece que no podemos utilizar el enfoque de clasificación con tales requisitos. ¿Qué pasa con esto? Construya un histograma de elementos, si algún elemento tiene una frecuencia relativa mayor que 0.5, la matriz es plural. La complejidad de Algo dependerá de la complejidad de búsqueda/inserción de tabla de histograma. ¿O este enfoque también viola la regla de no-less/greater-operators? (porque todavía tenemos que verificar frecuencia más grande que 0.5) :-) –

si los elementos son comparables, el algoritmo no está limitado a la velocidad de clasificación. –

Dado que es una tarea, aquí hay pistas: deberías poder probarlas fácilmente y terminar la pregunta.

Una matriz de elemento individual tiene trivialmente un elemento plural
Una matriz tiene a lo sumo un elemento plural, supongamos que existe y llamarlo x.
Si divide la matriz en dos mitades, x será un elemento plural de al menos un de las mitades.

Fuente

2011-03-01 19:01:40

¡Hola, Chris! Esto es lo que tengo hasta ahora. El requisito es que sea un algoritmo de división y conquista. Así que voy a romper la matriz en los subarrays de 2 elementos. 'Comparar los 2 elementos, Si es EQUAL, guárdelo en otra matriz Si NO ES IGUAL, deseche los 2 elementos.' después de pasar por todos los elementos, tendré una nueva matriz. en el ejemplo di 'aa ab bc ac ===> resulta en tener una en la nueva matriz.' pero dado que solo hay 4 a's en la matriz, no es una matriz plural. por lo tanto, tendría que pasar por la matriz de nuevo para verificar si ese elemento es un elemento plural. – ali

Entonces, ¿O (n) de la verificación vincula la complejidad del algoritmo? o sería O (nlgn) debido a la etapa de división del algoritmo. – ali

Estás muy cerca. * Siempre * tendrá que ejecutar nuevamente la matriz para verificar. Por ejemplo, si su matriz es aaaabbbb, y divide y conquista a aaaa | bbbb, esos subcampos son plurales (a y b), y * tiene * para contar los a y los b para verificar que ninguno de los dos es plural en el original. Tenías razón, es O (n lg n) - es el paso de verificación (verificando tantos como n elementos, en tantos niveles LGg de subdivisión). –

Dividir y conquistar - Array plural

Respuesta

Cuestiones relacionadas