Sí, el enfoque de búsqueda binaria se puede aplicar aquí.
Considere este caso de prueba:
9 3 5
- ¿Puedes darme una idea para un juego simple que implemente el algoritmo (como el algoritmo A *) o la inteligencia artificial para NPC en el juego?
- ¿Cómo se puede calcular el número de inversiones entre dos matrices en O (N log N)?
- ¿En qué programas podemos practicar para comprender la programación y los algoritmos?
- ¿Hay números irracionales de distribución uniforme no repetitivos para los cuales el dígito n puede calcularse en O (1) tiempo?
- ¿Cuál es el algoritmo utilizado para convertir cadenas en enteros?
2 4 7
Entonces, la matriz resultante después de la eliminación será: 1 3 5 6 8 9
Dado que 8 está en el índice 5 (indexación 1), por lo tanto, la respuesta es 8
La clave para aplicar la búsqueda binaria es encontrar una función monótona. Entonces, ¿cuál es esa función en este problema?
Comparemos los índices iniciales y finales de los números en la matriz.
1: (inicial = 1, final = 1)
3: (inicial = 3, final = 2)
5: (5,3), 6: (6,4), 8: (8,5), 9: (9,6)
Entonces, final-inicial para cada valor es:
0 1 2 2 3 3
Voila! hemos encontrado nuestra función monótona, y eso es
f (x) = índice de x en la matriz final-índice de x en la matriz inicial
(el dominio de f es todos los valores presentes en la matriz final)
Entonces, ¿cómo codificar esto en forma de búsqueda binaria para encontrar la respuesta correcta?
tome el límite inferior para que la búsqueda binaria sea 1, y el límite superior cualquier valor solo mayor que N (es decir, 1e9). Ahora, para cada valor medio, repita la matriz de valores eliminados y cuente los valores que sean menores o iguales que el valor medio . (por ejemplo, almacena conteo en variable cnt )
¿Por qué estamos haciendo esto? porque necesitamos encontrar el nuevo índice de este valor medio.
¿Cómo encontrar el nuevo índice? Es muy facil. El nuevo índice está a mitad de camino . La razón de esto es que inicialmente el índice de valor medio era medio, y ahora después de eliminar todos los elementos menores o iguales al valor medio, el índice de valor medio ha disminuido en ese recuento.
largo largo int bajo = 1, alto = 1e9 + 10, medio, cnt;
mientras (bajo <alto)
{
medio = (bajo + alto) / 2;
cnt = 0;
para (int i = 0; i <k; i ++)
{
if (a [i] <= mid) cnt ++;
}
if (mid-cnt> = p) high = mid;
más bajo = medio + 1;
}
if (r <= n) cout << r << endl;
else cout << – 1 << endl; // idx p está fuera de la matriz final de tamaño Nk
La complejidad del tiempo será O (k * lgN)
¡Espero eso ayude!
