Dados dos enteros L y R y una array arr[] que consta de N enteros positivos ( indexación basada en 1 ) tal que la frecuencia del i -ésimo elemento de una secuencia ordenada, digamos A[] , es arr[i] . La tarea es encontrar el número de elementos distintos del rango [L, R] en la secuencia A[] .
Ejemplos:
Entrada: arr[] = {3, 6, 7, 1, 8}, L = 3, R = 7
Salida: 2
Explicación: De la array de frecuencia dada, la array ordenada será {1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, ….}. Ahora, el número de elementos distintos del rango [3, 7] es 2 ( = {1, 2}).Entrada: arr[] = {1, 2, 3, 4}, L = 3, R = 4
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es construir la secuencia ordenada a partir de la array dada arr[] usando las frecuencias dadas y luego atravesar la array construida sobre el rango [L, R] para contar el número de elementos distintos.
Complejidad de tiempo: O(N + R – L)
Espacio auxiliar: O(S), donde S es la suma de los elementos del arreglo .
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la búsqueda binaria y la técnica de suma de prefijos para encontrar la cantidad de elementos distintos en el rango [L, R]. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array auxiliar, digamos prefijo[] que almacena la suma de prefijos de los elementos de array dados.
- Encuentre la suma del prefijo de la array dada y guárdela en el prefijo de la array [] .
- Al utilizar la búsqueda binaria, encuentre el primer índice en el que el valor en prefix[] sea al menos L , digamos left .
- Al utilizar la búsqueda binaria, encuentre el primer índice en el que el valor en prefix[] sea al menos R , digamos right .
- Después de completar los pasos anteriores, imprima el valor de (derecha – izquierda + 1) como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find the first index
// with value is at least element
int binarysearch(int array[], int right,
int element)
{
// Update the value of left
int left = 1;
// Update the value of right
// Binary search for the element
while (left <= right)
{
// Find the middle element
int mid = (left + right / 2);
if (array[mid] == element)
{
return mid;
}
// Check if the value lies
// between the elements at
// index mid - 1 and mid
if (mid - 1 > 0 && array[mid] > element &&
array[mid - 1] < element)
{
return mid;
}
// Check in the right subarray
else if (array[mid] < element)
{
// Update the value
// of left
left = mid + 1;
}
// Check in left subarray
else
{
// Update the value of
// right
right = mid - 1;
}
}
return 1;
}
// Function to count the number of
// distinct elements over the range
// [L, R] in the sorted sequence
void countDistinct(vector<int> arr,
int L, int R)
{
// Stores the count of distinct
// elements
int count = 0;
// Create the prefix sum array
int pref[arr.size() + 1];
for(int i = 1; i <= arr.size(); ++i)
{
// Update the value of count
count += arr[i - 1];
// Update the value of pref[i]
pref[i] = count;
}
// Calculating the first index
// of L and R using binary search
int left = binarysearch(pref, arr.size() + 1, L);
int right = binarysearch(pref, arr.size() + 1, R);
// Print the resultant count
cout << right - left + 1;
}
// Driver Code
int main()
{
vector<int> arr{ 3, 6, 7, 1, 8 };
int L = 3;
int R = 7;
countDistinct(arr, L, R);
}
// This code is contributed by ipg2016107
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the first index
// with value is at least element
static int binarysearch(int array[],
int element)
{
// Update the value of left
int left = 1;
// Update the value of right
int right = array.length - 1;
// Binary search for the element
while (left <= right) {
// Find the middle element
int mid = (int)(left + right / 2);
if (array[mid] == element) {
return mid;
}
// Check if the value lies
// between the elements at
// index mid - 1 and mid
if (mid - 1 > 0
&& array[mid] > element
&& array[mid - 1] < element) {
return mid;
}
// Check in the right subarray
else if (array[mid] < element) {
// Update the value
// of left
left = mid + 1;
}
// Check in left subarray
else {
// Update the value of
// right
right = mid - 1;
}
}
return 1;
}
// Function to count the number of
// distinct elements over the range
// [L, R] in the sorted sequence
static void countDistinct(int arr[],
int L, int R)
{
// Stores the count of distinct
// elements
int count = 0;
// Create the prefix sum array
int pref[] = new int[arr.length + 1];
for (int i = 1; i <= arr.length; ++i) {
// Update the value of count
count += arr[i - 1];
// Update the value of pref[i]
pref[i] = count;
}
// Calculating the first index
// of L and R using binary search
int left = binarysearch(pref, L);
int right = binarysearch(pref, R);
// Print the resultant count
System.out.println(
(right - left) + 1);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 6, 7, 1, 8 };
int L = 3;
int R = 7;
countDistinct(arr, L, R);
}
}
Python3
# Python3 program for the above approach # Function to find the first index # with value is at least element def binarysearch(array, right, element): # Update the value of left left = 1 # Update the value of right # Binary search for the element while (left <= right): # Find the middle element mid = (left + right // 2) if (array[mid] == element): return mid # Check if the value lies # between the elements at # index mid - 1 and mid if (mid - 1 > 0 and array[mid] > element and array[mid - 1] < element): return mid # Check in the right subarray elif (array[mid] < element): # Update the value # of left left = mid + 1 # Check in left subarray else: # Update the value of # right right = mid - 1 return 1 # Function to count the number of # distinct elements over the range # [L, R] in the sorted sequence def countDistinct(arr, L, R): # Stores the count of distinct # elements count = 0 # Create the prefix sum array pref = [0] * (len(arr) + 1) for i in range(1, len(arr) + 1): # Update the value of count count += arr[i - 1] # Update the value of pref[i] pref[i] = count # Calculating the first index # of L and R using binary search left = binarysearch(pref, len(arr) + 1, L) right = binarysearch(pref, len(arr) + 1, R) # Print the resultant count print(right - left + 1) # Driver Code if __name__ == "__main__": arr = [ 3, 6, 7, 1, 8 ] L = 3 R = 7 countDistinct(arr, L, R) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the first index
// with value is at least element
static int binarysearch(int []array, int right,
int element)
{
// Update the value of left
int left = 1;
// Update the value of right
// Binary search for the element
while (left <= right)
{
// Find the middle element
int mid = (left + right / 2);
if (array[mid] == element)
{
return mid;
}
// Check if the value lies
// between the elements at
// index mid - 1 and mid
if (mid - 1 > 0 && array[mid] > element &&
array[mid - 1] < element)
{
return mid;
}
// Check in the right subarray
else if (array[mid] < element)
{
// Update the value
// of left
left = mid + 1;
}
// Check in left subarray
else
{
// Update the value of
// right
right = mid - 1;
}
}
return 1;
}
// Function to count the number of
// distinct elements over the range
// [L, R] in the sorted sequence
static void countDistinct(List<int> arr,
int L, int R)
{
// Stores the count of distinct
// elements
int count = 0;
// Create the prefix sum array
int []pref = new int[arr.Count + 1];
for(int i = 1; i <= arr.Count; ++i)
{
// Update the value of count
count += arr[i - 1];
// Update the value of pref[i]
pref[i] = count;
}
// Calculating the first index
// of L and R using binary search
int left = binarysearch(pref, arr.Count + 1, L);
int right = binarysearch(pref, arr.Count + 1, R);
// Print the resultant count
Console.Write(right - left + 1);
}
// Driver Code
public static void Main()
{
List<int> arr = new List<int>(){ 3, 6, 7, 1, 8 };
int L = 3;
int R = 7;
countDistinct(arr, L, R);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
// Function to find the first index
// with value is at least element
function binarysearch(array, right, element)
{
// Update the value of left
let left = 1;
// Update the value of right
// Binary search for the element
while (left <= right)
{
// Find the middle element
let mid = Math.floor((left + right / 2));
if (array[mid] == element)
{
return mid;
}
// Check if the value lies
// between the elements at
// index mid - 1 and mid
if (mid - 1 > 0 && array[mid] > element &&
array[mid - 1] < element)
{
return mid;
}
// Check in the right subarray
else if (array[mid] < element)
{
// Update the value
// of left
left = mid + 1;
}
// Check in left subarray
else
{
// Update the value of
// right
right = mid - 1;
}
}
return 1;
}
// Function to count the number of
// distinct elements over the range
// [L, R] in the sorted sequence
function countDistinct(arr, L, R)
{
// Stores the count of distinct
// elements
let count = 0;
// Create the prefix sum array
let pref = Array.from(
{length: arr.length + 1}, (_, i) => 0);
for(let i = 1; i <= arr.length; ++i)
{
// Update the value of count
count += arr[i - 1];
// Update the value of pref[i]
pref[i] = count;
}
// Calculating the first index
// of L and R using binary search
let left = binarysearch(pref, arr.length + 1, L);
let right = binarysearch(pref, arr.length + 1, R);
// Print the resultant count
document.write((right - left) + 1);
}
// Driver Code
let arr = [ 3, 6, 7, 1, 8 ];
let L = 3;
let R = 7;
countDistinct(arr, L, R);
// This code is contributed by susmitakundugoaldanga
</script>
Producción:
2
Complejidad de tiempo: O(log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA