Dada una array binaria ordenada en orden no creciente, cuente el número de 1 en ella.
Ejemplos:
Input: arr[] = {1, 1, 0, 0, 0, 0, 0}
Output: 2
Input: arr[] = {1, 1, 1, 1, 1, 1, 1}
Output: 7
Input: arr[] = {0, 0, 0, 0, 0, 0, 0}
Output: 0
Una solución simple es atravesar linealmente la array. La complejidad temporal de la solución simple es O(n). Podemos usar la búsqueda binaria para encontrar el conteo en el tiempo O (Inicio de sesión). La idea es buscar la última aparición de 1 utilizando la búsqueda binaria. Una vez que encontramos la última ocurrencia del índice, devolvemos el índice + 1 como conteo.
La siguiente es la implementación de la idea anterior.
PHP
<?php
// PHP program to count one's in a
// boolean array
/* Returns counts of 1's in arr[low..high].
The array is assumed to be sorted in
non-increasing order */
function countOnes( $arr, $low, $high)
{
if ($high >= $low)
{
// get the middle index
$mid = $low + ($high - $low)/2;
// check if the element at middle
// index is last 1
if ( ($mid == $high or $arr[$mid+1] == 0)
and ($arr[$mid] == 1))
return $mid+1;
// If element is not last 1, recur for
// right side
if ($arr[$mid] == 1)
return countOnes($arr, ($mid + 1),
$high);
// else recur for left side
return countOnes($arr, $low, ($mid -1));
}
return 0;
}
/* Driver code */
$arr = array(1, 1, 1, 1, 0, 0, 0);
$n = count($arr);
echo "Count of 1's in given array is " ,
countOnes($arr, 0, $n-1);
// This code is contributed by anuj_67.
?>
Count of 1's in given array is 4
La complejidad temporal de la solución anterior es O (Iniciar sesión)
Complejidad espacial o(log n) (pila de llamadas de función)
Consulte el artículo completo sobre Count 1’s en una array binaria 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