Consultas de recuentos de elementos de array con valores en un rango dado

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:

// 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;
}

// 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

# 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))

// 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
// 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
?>

<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:

// 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;
}

// 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.

# 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))

// 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
// 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
?>

<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.