PUERTA | PUERTA CS 2008 | Pregunta 40

El número mínimo de comparaciones requeridas para determinar si un entero aparece más de n/2 veces en una array ordenada de n enteros es

(A) Θ(n)
(B) Θ(logn)
(C) Θ(log*n)
(D) Θ(1)

Respuesta: (B)
Explicación: Si respondió Theta(1), piense en ejemplos { 1, 2, 2, 2, 4, 4}, {1, 1, 2, 2, 2, 2, 3, 3}

La mejor manera de averiguar si un número entero aparece más de n/2 veces en una array ordenada (orden ascendente) de n enteros sería el enfoque de búsqueda binaria.

1. La primera aparición de un elemento se puede encontrar en el tiempo O (log (n)) usando la técnica de divide y vencerás, digamos que es i.
2. La última aparición de un elemento se puede encontrar en el tiempo O (log (n)) usando la técnica de divide y vencerás, digamos que es j.
3. Ahora el número de ocurrencias de ese elemento (recuento) es (j-i+1). Complejidad total del tiempo = log n +log n +1 = O(logn)

Consulte Comprobar el elemento mayoritario en una array ordenada

Esta solución es aportada por Nirmal Bharadwaj
Cuestionario de esta pregunta