给定一个大小为n的未排序数组，在两个元素i和j（均包含）之间找不到任何元素。 例如：
null
Input : arr = [1 3 3 9 10 4] i1 = 1, j1 = 4 i2 = 9, j2 = 12Output : 4 2The numbers are: 1 3 3 4 for first queryThe numbers are: 9 10 for second query
资料来源： 亚马逊面试经验
A. 简单方法 将运行for循环，检查每个元素是否在给定范围内，并保持其计数。运行每个查询的时间复杂度为O（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 ). "" ; $i = 9; $j = 12; echo countInRange( $arr , $n , $i , $j ). "" ; // 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> |
输出：
42
一 有效的方法 将首先对数组进行排序，然后使用改进的二进制搜索函数查找两个索引，第一个元素大于或等于范围下限，另一个元素小于或等于范围上限。运行每个查询的时间为O（logn），对数组进行一次排序的时间为O（nlogn）。
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 ), "" ; $i = 9; $j = 12; echo countInRange( $arr , $n , $i , $j ), "" ; // 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> |
输出：
42
本文由 阿迪蒂·夏尔马 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
