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.
Python
# Python 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
def 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=[1, 1, 1, 1, 0, 0, 0]
print ("Count of 1's in given array is",countOnes(arr, 0 , len(arr)-1))
# This code is contributed by __Devesh Agrawal__
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