Dada una array de n enteros. Te dan q consultas. Escriba un programa para imprimir el valor mínimo de la media en el rango de l a r para cada consulta en una nueva línea.
Ejemplos:
Input : arr[] = {1, 2, 3, 4, 5} q = 3 0 2 1 3 0 4 Output : 2 3 3 Here for 0 to 2 (1 + 2 + 3) / 3 = 2 Input : arr[] = {6, 7, 8, 10} q = 2 0 3 1 2 Output : 7 7
Enfoque ingenuo: podemos ejecutar un ciclo para cada consulta de l a r y encontrar la suma y el número de elementos en el rango. Después de esto, podemos imprimir el piso de la media para cada consulta.
Python3
# Python 3 program to find floor value # of mean in range l to r import math # To find mean of range in l to r def findMean(arr, l, r): # Both sum and count are # initialize to 0 sum, count = 0, 0 # To calculate sum and number # of elements in range l to r for i in range(l, r + 1): sum += arr[i] count += 1 # Calculate floor value of mean mean = math.floor(sum / count) # Returns mean of array # in range l to r return mean # Driver Code arr = [ 1, 2, 3, 4, 5 ] print(findMean(arr, 0, 2)) print(findMean(arr, 1, 3)) print(findMean(arr, 0, 4)) # This code is contributed # by PrinciRaj1992
Producción :
2 3 3
Complejidad temporal: O(n*q) donde q es el número de consultas y n es el tamaño de la array. Aquí, en el código anterior, q es 3 ya que la función findMean se usa 3 veces.
Espacio Auxiliar: O(1)
Enfoque eficiente: podemos encontrar la suma de números usando números usando el prefijo sum . El prefixSum[i] denota la suma de los primeros i elementos. Entonces, la suma de los números en el rango de l a r será prefixSum[r] – prefixSum[l-1]. El número de elementos en el rango de l a r será r – l + 1. Entonces ahora podemos imprimir la media del rango de l a r en O(1).
Python3
# Python3 program to find floor value # of mean in range l to r import math as mt MAX = 1000005 prefixSum = [0 for i in range(MAX)] # To calculate prefixSum of array def calculatePrefixSum(arr, n): # Calculate prefix sum of array prefixSum[0] = arr[0] for i in range(1,n): prefixSum[i] = prefixSum[i - 1] + arr[i] # To return floor of mean # in range l to r def findMean(l, r): if (l == 0): return mt.floor(prefixSum[r] / (r + 1)) # Sum of elements in range l to # r is prefixSum[r] - prefixSum[l-1] # Number of elements in range # l to r is r - l + 1 return (mt.floor((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1))) # Driver Code arr = [1, 2, 3, 4, 5] n = len(arr) calculatePrefixSum(arr, n) print(findMean(0, 2)) print(findMean(1, 3)) print(findMean(0, 4)) # This code is contributed by Mohit Kumar
Producción:
2 3 3
Complejidad temporal: O(n+q) donde q es el número de consultas y n es el tamaño de la array. Aquí, en el código anterior, q es 3 ya que la función findMean se usa 3 veces.
Espacio Auxiliar: O(k) donde k=1000005.
Consulte el artículo completo sobre la media del rango en una array 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