[Requisitos de la pregunta] darle n números y n. Ahora debe encontrar el número que ocurre más del 50% de las veces en el espacio O (N) dentro de O (1).
[Iniciar mierda] Al principio, vi esta pregunta cegada instantáneamente (TOT)/~~~ (.*). Si solo existe el requisito de tiempo de O (N), se puede resolver instantáneamente con hash (es decir, con espacio para el tiempo), y parece difícil resolver el espacio de O (1).
[Pensamiento 1] Doble bucle, esta es la forma menos eficiente de resolver este problema, es decir, calcule el número de veces que aparece para cada número, y la complejidad del tiempo o (n^2) está directamente fuera.
[Pensamiento 2] Primero, deje que los números similares se organicen juntos y luego atraviesen el primer número. Ahora dé un ejemplo, como: 1000012, ahora ordene: 0000112, comience desde 0, establezca un contador t = 0, ahora hay 4 0s, luego t = 4, encuentre que más de la mitad de ellos, la salida 0. Este método es la versión optimizada del método anterior.
[Pensamiento 3] Es la idea de intercambiar espacio por el tiempo y el hashing para hacer que una matriz unidimensional tenga dos significados. Por ejemplo, A [x] = y representa que el número x aparece y veces. La complejidad del tiempo de este método es o (n), pero el espacio es realmente ... no hablaré de eso (* ￣￣) fuera
[Pensamiento 4] Primero calcule la probabilidad, seleccione el número de estos números que tienen más probabilidades de cumplir con los requisitos y luego seleccionan aleatoriamente algunos. Esto ... olvídalo.
[Pensamiento 5] El tema de hoy es el llamado algoritmo Mjrty, también conocido como el algoritmo de votación mayoritario. Las ideas principales son las siguientes: (¡La complejidad del tiempo de este algoritmo es O (N)! ¡No hay necesidad de almacenamiento adicional en el espacio, por lo que la complejidad del espacio es O (1)!
Si count == 0, establezca el valor de voto en el elemento actual de la matriz y asigne un recuento a 1;
De lo contrario, si el voto y ahora los elementos de matriz tienen el mismo valor, cuente ++, de lo contrario, cuente;
Repita los dos pasos anteriores hasta que se escanee la matriz.
El recuento se asigna a 0 y escanea la matriz nuevamente desde el principio. Si el valor del elemento de matriz es el mismo que el valor del voto, cuente ++ hasta que se escanee la matriz.
Si el valor del recuento es mayor o igual a N/2 en este momento, se devolverá el valor del voto, de lo contrario, se devolverá -1;
La siguiente es la implementación del código. Dado que la pregunta asegura que el resultado debe existir, omitimos el último paso de verificación y verificación.
El código clave es el siguiente:
#InClude <Iostream> Usando el espacio de nombres std; int len; void find (int* a, int n) {char candidato; int ntimes, i; for (i = ntimes = 0; i <n; i ++) {if (ntimes == 0) candidato = a [i], nTimes = 1; else {if (candidato == a [i]) nTimes ++; else nTimes-;}} cout << candidato candidato; } int main () {cin >> len; intLo anterior es el número de más de la mitad (50%) del número de ocurrencias introducidos por el editor. Espero que te sea útil. Si tiene alguna pregunta, déjame un mensaje y el editor le responderá a tiempo. ¡Muchas gracias por su apoyo al sitio web de Wulin.com!