Dada una array desordenada de tamaño n, encuentre el número de elementos entre dos elementos i y j (ambos inclusive).
Ejemplos:
Input : arr = [1 3 3 9 10 4] i1 = 1, j1 = 4 i2 = 9, j2 = 12 Output : 4 2 The numbers are: 1 3 3 4 for first query The numbers are: 9 10 for second query
Fuente: experiencia de entrevista de Amazon
Un enfoque simple será ejecutar un ciclo for para verificar si cada elemento está en el rango dado y mantener su conteo. La complejidad del tiempo para ejecutar cada consulta será O(n).
Implementación:
C++
// Simple C++ program to count number of elements // with values in given range. #include <bits/stdc++.h> using namespace std; // function to count elements within given range int countInRange(int arr[], int n, int x, int y) { // initialize result int count = 0; for (int i = 0; i < n; i++) { // check if element is in range if (arr[i] >= x && arr[i] <= y) count++; } return count; } // driver function int main() { int arr[] = { 1, 3, 4, 9, 10, 3 }; int n = sizeof(arr) / sizeof(arr[0]); // Answer queries int i = 1, j = 4; cout << countInRange(arr, n, i, j) << endl; i = 9, j = 12; cout << countInRange(arr, n, i, j) << endl; return 0; }
Java
// Simple java program to count // number of elements with // values in given range. import java.io.*; class GFG { // function to count elements within given range static int countInRange(int arr[], int n, int x, int y) { // initialize result int count = 0; for (int i = 0; i < n; i++) { // check if element is in range if (arr[i] >= x && arr[i] <= y) count++; } return count; } // driver function public static void main (String[] args) { int arr[] = { 1, 3, 4, 9, 10, 3 }; int n = arr.length; // Answer queries int i = 1, j = 4; System.out.println ( countInRange(arr, n, i, j)) ; i = 9; j = 12; System.out.println ( countInRange(arr, n, i, j)) ; } } // This article is contributed by vt_m
Python3
# function to count elements within given range def countInRange(arr, n, x, y): # initialize result count = 0; for i in range(n): # check if element is in range if (arr[i] >= x and arr[i] <= y): count += 1 return count # driver function arr = [1, 3, 4, 9, 10, 3] n = len(arr) # Answer queries i = 1 j = 4 print(countInRange(arr, n, i, j)) i = 9 j = 12 print(countInRange(arr, n, i, j))
C#
// Simple C# program to count // number of elements with // values in given range. using System; class GFG { // function to count elements // within given range static int countInRange(int []arr, int n, int x, int y) { // initialize result int count = 0; for (int i = 0; i < n; i++) { // check if element is in range if (arr[i] >= x && arr[i] <= y) count++; } return count; } // Driver Code public static void Main () { int[]arr = {1, 3, 4, 9, 10, 3}; int n = arr.Length; // Answer queries int i = 1, j = 4; Console.WriteLine( countInRange(arr, n, i, j)) ; i = 9; j = 12; Console.WriteLine( countInRange(arr, n, i, j)) ; } } // This code is contributed by vt_m.
PHP
<?php // Simple PHP program to count // number of elements with // values in given range. // function to count elements // within given range function countInRange($arr, $n, $x, $y) { // initialize result $count = 0; for ($i = 0; $i < $n; $i++) { // check if element is in range if ($arr[$i] >= $x && $arr[$i] <= $y) $count++; } return $count; } // Driver Code $arr = array(1, 3, 4, 9, 10, 3); $n = count($arr); // Answer queries $i = 1; $j = 4; echo countInRange($arr, $n, $i, $j)."\n"; $i = 9; $j = 12; echo countInRange($arr, $n, $i, $j)."\n"; // This code is contributed by Sam007 ?>
Javascript
<script> // Simple JavaScript program to count // number of elements with // values in given range. // function to count elements // within given range function countInRange(arr, n, x, y) { // initialize result let count = 0; for (let i = 0; i < n; i++) { // check if element is in range if (arr[i] >= x && arr[i] <= y) count++; } return count; } let arr = [1, 3, 4, 9, 10, 3]; let n = arr.length; // Answer queries let i = 1, j = 4; document.write( countInRange(arr, n, i, j) + "</br>") ; i = 9; j = 12; document.write( countInRange(arr, n, i, j)) ; </script>
4 2
Complejidad de Tiempo: O(n),
Espacio Auxiliar: O(1)
Un enfoque eficiente será ordenar primero la array y luego usar una función de búsqueda binaria modificada para encontrar dos índices, uno del primer elemento mayor o igual al límite inferior del rango y el otro del último elemento menor o igual al límite superior. El tiempo para ejecutar cada consulta será O(logn) y para ordenar la array una vez será O(nlogn).
Implementación:
C++
// Efficient C++ program to count number of elements // with values in given range. #include <bits/stdc++.h> using namespace std; // function to find first index >= x int lowerIndex(int arr[], int n, int x) { int l = 0, h = n - 1; while (l <= h) { int mid = (l + h) / 2; if (arr[mid] >= x) h = mid - 1; else l = mid + 1; } return l; } // function to find last index <= y int upperIndex(int arr[], int n, int y) { int l = 0, h = n - 1; while (l <= h) { int mid = (l + h) / 2; if (arr[mid] <= y) l = mid + 1; else h = mid - 1; } return h; } // function to count elements within given range int countInRange(int arr[], int n, int x, int y) { // initialize result int count = 0; count = upperIndex(arr, n, y) - lowerIndex(arr, n, x) + 1; return count; } // driver function int main() { int arr[] = { 1, 4, 4, 9, 10, 3 }; int n = sizeof(arr) / sizeof(arr[0]); // Preprocess array sort(arr, arr + n); // Answer queries int i = 1, j = 4; cout << countInRange(arr, n, i, j) << endl; i = 9, j = 12; cout << countInRange(arr, n, i, j) << endl; return 0; }
Java
// Efficient C++ program to count number // of elements with values in given range. import java.io.*; import java.util.Arrays; class GFG { // function to find first index >= x static int lowerIndex(int arr[], int n, int x) { int l = 0, h = n - 1; while (l <= h) { int mid = (l + h) / 2; if (arr[mid] >= x) h = mid - 1; else l = mid + 1; } return l; } // function to find last index <= y static int upperIndex(int arr[], int n, int y) { int l = 0, h = n - 1; while (l <= h) { int mid = (l + h) / 2; if (arr[mid] <= y) l = mid + 1; else h = mid - 1; } return h; } // function to count elements within given range static int countInRange(int arr[], int n, int x, int y) { // initialize result int count = 0; count = upperIndex(arr, n, y) - lowerIndex(arr, n, x) + 1; return count; } // Driver function public static void main (String[] args) { int arr[] = { 1, 4, 4, 9, 10, 3 }; int n = arr.length; // Preprocess array Arrays.sort(arr); // Answer queries int i = 1, j = 4; System.out.println( countInRange(arr, n, i, j)); ; i = 9; j = 12; System.out.println( countInRange(arr, n, i, j)); } } // This article is contributed by vt_m.
Python3
# function to find first index >= x def lowerIndex(arr, n, x): l = 0 h = n-1 while (l <= h): mid = int((l + h)//2) if (arr[mid] >= x): h = mid - 1 else: l = mid + 1 return l # function to find last index <= x def upperIndex(arr, n, x): l = 0 h = n-1 while (l <= h): mid = int((l + h)//2) if (arr[mid] <= x): l = mid + 1 else: h = mid - 1 return h # function to count elements within given range def countInRange(arr, n, x, y): # initialize result count = 0; count = upperIndex(arr, n, y) - lowerIndex(arr, n, x) + 1; return count # driver function arr = [1, 3, 4, 9, 10, 3] # Preprocess array arr.sort() n = len(arr) # Answer queries i = 1 j = 4 print(countInRange(arr, n, i, j)) i = 9 j = 12 print(countInRange(arr, n, i, j))
C#
// Efficient C# program to count number // of elements with values in given range. using System; class GFG { // function to find first index >= x static int lowerIndex(int []arr, int n, int x) { int l = 0, h = n - 1; while (l <= h) { int mid = (l + h) / 2; if (arr[mid] >= x) h = mid - 1; else l = mid + 1; } return l; } // function to find last index <= y static int upperIndex(int []arr, int n, int y) { int l = 0, h = n - 1; while (l <= h) { int mid = (l + h) / 2; if (arr[mid] <= y) l = mid + 1; else h = mid - 1; } return h; } // function to count elements // within given range static int countInRange(int []arr, int n, int x, int y) { // initialize result int count = 0; count = upperIndex(arr, n, y) - lowerIndex(arr, n, x) + 1; return count; } // Driver code public static void Main () { int []arr = {1, 4, 4, 9, 10, 3}; int n = arr.Length; // Preprocess array Array.Sort(arr); // Answer queries int i = 1, j = 4; Console.WriteLine(countInRange(arr, n, i, j)); ; i = 9; j = 12; Console.WriteLine(countInRange(arr, n, i, j)); } } // This code is contributed by vt_m.
PHP
<?php // Efficient PHP program to count // number of elements with values // in given range. // function to find first index >= x function lowerIndex($arr, $n, $x) { $l = 0; $h = $n - 1; while ($l <= $h) { $mid = ($l + $h) / 2; if ($arr[$mid] >= $x) $h = $mid - 1; else $l = $mid + 1; } return $l; } // function to find last index <= y function upperIndex($arr, $n, $y) { $l = 0; $h = $n - 1; while ($l <= $h) { $mid = ($l + $h) / 2; if ($arr[$mid] <= $y) $l = $mid + 1; else $h = $mid - 1; } return $h; } // function to count elements // within given range function countInRange($arr, $n, $x, $y) { // initialize result $count = 0; $count = (upperIndex($arr, $n, $y) - lowerIndex($arr, $n, $x) + 1); $t = floor($count); return $t; } // Driver Code $arr = array( 1, 4, 4, 9, 10, 3 ); $n = sizeof($arr); // Preprocess array sort($arr); // Answer queries $i = 1; $j = 4; echo countInRange($arr, $n, $i, $j), "\n"; $i = 9; $j = 12; echo countInRange($arr, $n, $i, $j), "\n"; // This code is contributed by Sachin ?>
Javascript
<script> // Efficient Javascript program to count number // of elements with values in given range. // function to find first index >= x function lowerIndex(arr, n, x) { let l = 0, h = n - 1; while (l <= h) { let mid = parseInt((l + h) / 2, 10); if (arr[mid] >= x) h = mid - 1; else l = mid + 1; } return l; } // function to find last index <= y function upperIndex(arr, n, y) { let l = 0, h = n - 1; while (l <= h) { let mid = parseInt((l + h) / 2, 10); if (arr[mid] <= y) l = mid + 1; else h = mid - 1; } return h; } // function to count elements // within given range function countInRange(arr, n, x, y) { // initialize result let count = 0; count = upperIndex(arr, n, y) - lowerIndex(arr, n, x) + 1; return count; } let arr = [1, 4, 4, 9, 10, 3]; let n = arr.length; // Preprocess array arr.sort(function(a, b){return a - b}); // Answer queries let i = 1, j = 4; document.write(countInRange(arr, n, i, j) + "</br>"); ; i = 9; j = 12; document.write(countInRange(arr, n, i, j)); </script>
4 2
Complejidad de tiempo: O(n log n),
Espacio auxiliar: O(1)
Este artículo es una contribución de Aditi Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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