Pregunta: Escribe una función para encontrar si un entero x aparece más de n/2 veces en una array ordenada de n enteros.
Básicamente, necesitamos escribir una función, digamos isMajority(), que tome una array (arr[] ), el tamaño de la array (n) y un número para buscar (x) como parámetros y devuelva verdadero si x es un elemento mayoritario (presente más de n/2 veces).
Ejemplos:
Input: arr[] = {1, 2, 3, 3, 3, 3, 10}, x = 3
Output: True (x appears more than n/2 times in the given array)
Input: arr[] = {1, 1, 2, 4, 4, 4, 6, 6}, x = 4
Output: False (x doesn't appear more than n/2 times in the given array)
Input: arr[] = {1, 1, 1, 2, 2}, x = 1
Output: True (x appears more than n/2 times in the given array)
MÉTODO 1 (usando la búsqueda lineal) Busque
linealmente la primera aparición del elemento, una vez que lo encuentre (déjelo en el índice i), verifique el elemento en el índice i + n/2. Si el elemento está presente en i+n/2, devuelve 1; de lo contrario, devuelve 0.
Producción:
4 appears more than 3 times in arr[]
Complejidad de tiempo: O(n)
MÉTODO 2 (Usando la búsqueda binaria)
Use la metodología de búsqueda binaria para encontrar la primera ocurrencia del número dado. El criterio para la búsqueda binaria es importante aquí.
Javascript
<script>
// Javascript Program to check for majority
// element in a sorted array */
// If x is present in arr[low...high]
// then returns the index of first
// occurrence of x, otherwise returns -1
function _binarySearch(arr, low, high, x)
{
if (high >= low) {
let mid = parseInt((low + high) / 2, 10);
//low + (high - low)/2;
// Check if arr[mid] is the first
// occurrence of x. arr[mid] is
// first occurrence if x is one of
// the following is true:
// (i) mid == 0 and arr[mid] == x
// (ii) arr[mid-1] < x and arr[mid] == x
if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x))
return mid;
else if (x > arr[mid])
return _binarySearch(arr, (mid + 1), high, x);
else
return _binarySearch(arr, low, (mid - 1), x);
}
return -1;
}
// This function returns true if the x is
// present more than n/2 times in arr[]
// of size n
function isMajority(arr, n, x)
{
// Find the index of first occurrence
// of x in arr[]
let i = _binarySearch(arr, 0, n - 1, x);
// If element is not present at all,
// return false
if (i == -1)
return false;
// check if the element is present
// more than n/2 times
if (((i + parseInt(n / 2, 10)) <= (n - 1)) && arr[i + parseInt(n / 2, 10)] == x)
return true;
else
return false;
}
let arr = [ 1, 2, 3, 3, 3, 3, 10 ];
let n = arr.length;
let x = 3;
if (isMajority(arr, n, x) == true)
document.write(x + " appears more than " + parseInt(n / 2, 10) + " times in arr[]");
else
document.write(x + " does not appear more than " + parseInt(n / 2, 10) + " times in arr[]");
</script>
3 appears more than 3 times in arr[]
Complejidad temporal : O(1)
Espacio auxiliar: O(1)
Consulte el artículo completo sobre Comprobar el elemento mayoritario en una array ordenada para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA