Dado un arreglo de enteros bidimensional arr[] que representa N rangos, cada uno de tipo [start i , end i ] (start i , end i ≤ 10 9 ) y Q consultas representadas en el arreglo query[] , la tarea es encontrar el ocurrencia máxima de query[i] (query[i] ≤ 10 9 ) en los rangos dados para todos los i en el rango [0, Q-1] .
Ejemplos:
Entrada: arr[] = {{1, 5}, {3, 6}, {5, 7}, {12, 15}}, consulta[] = {1, 3, 5, 13} Salida: {
1 , 2, 3, 1}
Explicación: La ocurrencia de 1 en el rango es 1.
La ocurrencia de 3 en el rango es 2.
La ocurrencia de 5 en el rango es 3.
La ocurrencia de 13 en el rango es 1.Entrada: arr[] = {{2, 5}, {9, 11}, {3, 9}, {15, 20}}, consulta[] = {3, 9, 16, 55} Salida: {
2 , 2, 1, 0}
Enfoque ingenuo: para cada consulta, recorra la array y verifique si query[j] está en el rango de arr[i] = [start i , end i ] . Si está dentro del rango, incremente el contador para la aparición de ese elemento y almacene este contador correspondiente a consulta[j] en el resultado.
Complejidad temporal: O(Q * N)
Espacio auxiliar: O(1)
Enfoque eficiente: El problema se puede resolver en base a la siguiente idea:
Utilice la técnica de la suma de prefijos para almacenar las ocurrencias de cada elemento y ayudará a encontrar la respuesta para cada consulta en tiempo constante.
Siga los pasos a continuación para implementar la idea anterior:
- Declare una array unidimensional (digamos prefixSum[]) de longitud M (donde M es el elemento máximo en arr[]) para almacenar la ocurrencia de cada elemento.
- Iterar sobre la array arr[] y hacer lo siguiente para cada start i y end i :
- Incrementa el valor en prefixSum[start i ] en 1
- Disminuya el valor en prefixSum[end i + 1] en 1
- Iterar sobre la array prefixSum[] y calcular la suma del prefijo. Usando esto, se calcularán las ocurrencias de cada elemento en los rangos dados
- Itere sobre la array de consultas y para cada consulta obtenga el valor de prefixSum[query[i]] y guárdelo en la array resultante.
- Devuelve la array de resultados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000000
// Function to find occurrences of
// each element in array
void findTheOccurrence(vector<vector<int> >& arr,
vector<int>& q,
vector<int>& result)
{
vector<int> prefixSum(MAX);
// Iterating over arr
for (int i = 0; i < arr.size(); i++) {
int start = arr[i][0];
int end = arr[i][1];
// Increment the value of
// prefixSum at start
prefixSum[start]++;
// Decrement the value of
// prefixSum at end + 1
prefixSum[end + 1]--;
}
// Calculating the prefix sum
for (int i = 1; i < prefixSum.size(); i++) {
prefixSum[i]
= prefixSum[i - 1] + prefixSum[i];
}
// Resolving each queries
for (int i = 0; i < q.size(); i++) {
int occurrence = prefixSum[q[i]];
result.push_back(occurrence);
}
}
// Driver code
int main()
{
vector<vector<int> > arr
= { { 1, 5 }, { 3, 6 }, { 5, 7 }, { 12, 15 } };
vector<int> query = { 1, 3, 5, 13 };
vector<int> result;
// Function call
findTheOccurrence(arr, query, result);
for (auto i : result)
cout << i << " ";
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
static int MAX = 10000000;
// Function to find occurrences of
// each element in array
static void findTheOccurrence(int[][] arr, int[] q,
ArrayList<Integer> result)
{
int[] prefixSum = new int[(MAX)];
// Iterating over arr
for (int i = 0; i < arr.length; i++) {
int start = arr[i][0];
int end = arr[i][1];
// Increment the value of
// prefixSum at start
prefixSum[start]++;
// Decrement the value of
// prefixSum at end + 1
prefixSum[end + 1]--;
}
// Calculating the prefix sum
for (int i = 1; i < prefixSum.length; i++) {
prefixSum[i]
= prefixSum[i - 1] + prefixSum[i];
}
// Resolving each queries
for (int i = 0; i < q.length; i++) {
int occurrence = prefixSum[q[i]];
result.add(occurrence);
}
}
// Driver Code
public static void main(String args[])
{
int[][] arr
= { { 1, 5 }, { 3, 6 }, { 5, 7 }, { 12, 15 } };
int[] query = { 1, 3, 5, 13 };
ArrayList<Integer> result
= new ArrayList<Integer>();
// Function call
findTheOccurrence(arr, query, result);
for (int i : result)
System.out.print(i + " ");
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 code to implement the approach MAX = 10000; # Function to find occurrences of # each element in array def findTheOccurrence(arr, q, result): prefixSum = [0] * MAX # Iterating over arr for i in range(len(arr)): start = arr[i][0]; end = arr[i][1]; # Increment the value of # prefixSum at start prefixSum[start] += 1 # Decrement the value of # prefixSum at end + 1 prefixSum[end + 1] -= 1 # Calculating the prefix sum for i in range(1, len(prefixSum)): prefixSum[i] = prefixSum[i - 1] + prefixSum[i]; # Resolving each queries for i in range(0, len(q)): occurrence = prefixSum[q[i]]; result.append(occurrence); return result; # Driver code arr = [[ 1, 5 ], [ 3, 6 ], [ 5, 7 ], [ 12, 15 ] ]; query = [ 1, 3, 5, 13 ]; result = []; # Function call findTheOccurrence(arr, query, result); for i in range(len(result)): print(result[i], end=" "); # This code is contributed by Saurabh Jaiswal
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = 10000000;
// Function to find occurrences of
// each element in array
static void findTheOccurrence(int[,] arr, int[] q,
List<int> result)
{
int[] prefixSum = new int[(MAX)];
// Iterating over arr
for (int i = 0; i < arr.GetLength(0); i++) {
int start = arr[i, 0];
int end = arr[i, 1];
// Increment the value of
// prefixSum at start
prefixSum[start]++;
// Decrement the value of
// prefixSum at end + 1
prefixSum[end + 1]--;
}
// Calculating the prefix sum
for (int i = 1; i < prefixSum.Length; i++) {
prefixSum[i]
= prefixSum[i - 1] + prefixSum[i];
}
// Resolving each queries
for (int i = 0; i < q.Length; i++) {
int occurrence = prefixSum[q[i]];
result.Add(occurrence);
}
}
// Driver Code
public static void Main()
{
int[,] arr
= { { 1, 5 }, { 3, 6 }, { 5, 7 }, { 12, 15 } };
int[] query = { 1, 3, 5, 13 };
List<int> result
= new List<int>();
// Function call
findTheOccurrence(arr, query, result);
foreach (int i in result)
Console.Write(i + " ");
}
}
// This code is contributed by avijitmondal998.
Javascript
<script>
// JS code to implement the approach
let MAX = 10000;
// Function to find occurrences of
// each element in array
function findTheOccurrence(arr, q, result)
{
prefixSum = new Array(MAX).fill(0);
// Iterating over arr
for (var i = 0; i < arr.length; i++)
{
var start = arr[i][0];
var end = arr[i][1];
// Increment the value of
// prefixSum at start
prefixSum[start]++;
// Decrement the value of
// prefixSum at end + 1
prefixSum[end + 1]--;
}
// Calculating the prefix sum
for (var i = 1; i < prefixSum.length; i++) {
prefixSum[i] = prefixSum[i - 1] + prefixSum[i];
}
// Resolving each queries
for (var i = 0; i < q.length; i++) {
var occurrence = prefixSum[q[i]];
result.push(occurrence);
}
return result;
}
// Driver code
var arr = [[ 1, 5 ], [ 3, 6 ], [ 5, 7 ], [ 12, 15 ] ];
var query = [ 1, 3, 5, 13 ];
var result = [];
// Function call
findTheOccurrence(arr, query, result);
for (var i = 0; i < result.length; i++)
document.write(result[i] + " ");
// This code is contributed by phasing17
</script>
Producción
1 2 3 1
Complejidad temporal: O(M), donde M es el elemento máximo del arreglo.
Espacio Auxiliar: O(M)
Nota: este enfoque no funcionará aquí debido a las restricciones dadas
Enfoque optimizado para el espacio: la idea es similar al enfoque anterior, pero habrá los siguientes cambios:
Usaremos un mapa para almacenar la frecuencia de los elementos en rangos dados en lugar de crear una array de suma de prefijos . Si el rango de elementos en arr[] es alto como 10 9 , entonces no podemos crear una array de longitud tan grande. Pero en el mapa (mapa ordenado) podemos calcular la suma del prefijo mientras iteramos sobre el mapa y podemos realizar el resto de las operaciones como se hizo en el enfoque anterior.
Siga los pasos a continuación para implementar la idea anterior:
- Cree un mapa (mapa ordenado), donde la clave representa el elemento y el valor representa la frecuencia de la clave.
- Iterar sobre arr[] :
- Incrementa la frecuencia de inicio i en 1
- Decrementa la frecuencia de (end i + 1) en 1
- Inicialice dos arrays para almacenar los elementos que aparecen en el mapa y las frecuencias correspondientes a ese elemento.
- Itere sobre el mapa y use la técnica de suma de prefijos para calcular la frecuencia de cada elemento y almacenarlos en las arrays creadas.
- Iterar sobre la array de consulta y para cada consulta:
- Encuentre el número entero más cercano (digamos x ) que sea mayor o igual que query[i] y esté presente en el mapa.
- Compruebe si x y query[i] son iguales:
- Si son iguales, entonces la frecuencia correspondiente de x es la frecuencia requerida.
- De lo contrario, la respuesta es la frecuencia de los elementos correspondientes al elemento justo antes de x .
- Almacene esta frecuencia en la array resultante.
- Devuelve la array de resultados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the frequency
// of element in array arr
vector<int> findTheOccurrence(vector<vector<int> >& arr,
vector<int>& q,
vector<int>& result)
{
int n = arr.size();
// Map to store the elements
// with their frequency
map<long long, long long> mp;
for (auto& i : arr) {
mp[i[0]]++;
mp[(long long)i[1] + 1]--;
}
vector<long long> range, freq;
long long prefixSum = 0;
for (auto i : mp) {
// Calculate the frequency of element
// using prefix sum technique.
prefixSum = prefixSum
+ (long long)i.second;
// Store the element of arr in range
range.push_back(i.first);
// Store its corresponding frequency
freq.push_back(prefixSum);
}
// Iterate over the query
for (auto p : q) {
// Find the lower_bound of query p
int idx = lower_bound(range.begin(),
range.end(), p)
- range.begin();
// If the lower_bound doesn't exist
if (idx >= 0 && idx < range.size()) {
// Check if element
// which we are searching
// exists in the range or not.
// If it doesn't exist then
// lower bound will return
// the next element which is
// just greater than p
if (range[idx] != p)
idx--;
if (idx >= 0)
result.push_back(freq[idx]);
// If no such element exist
else
result.push_back(0);
}
// If idx is range size,
// it means all elements
// are smaller than p.
// So next smaller element will be
// at range.size() - 1
else {
result.push_back(freq[range.size()
- 1]);
}
}
// Return the final result
return result;
}
// Driver code
int main()
{
vector<vector<int> > arr
= { { 1, 5 }, { 3, 6 }, { 5, 7 }, { 12, 15 } };
vector<int> q = { 1, 3, 5, 13 };
vector<int> result;
// Function call
findTheOccurrence(arr, q, result);
for (auto i : result)
cout << i << " ";
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG
{
// This function returns the position
// of the leftmost array element that is
// greater than or equal to the key element
static int lower_bound(ArrayList<Integer> arr, int ele)
{
for (var i = 0; i < arr.size(); i++) {
if (arr.get(i) >= ele)
return i;
}
return arr.size();
}
// Function to find the frequency
// of element in array arr
static ArrayList<Integer>
findTheOccurrence(int[][] arr, int[] q,
ArrayList<Integer> result)
{
int n = arr.length;
// Map to store the elements
// with their frequency
TreeMap<Integer, Integer> mp
= new TreeMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
if (!mp.containsKey(arr[i][0]))
mp.put(arr[i][0], 0);
if (!mp.containsKey(arr[i][1] + 1))
mp.put(arr[i][1] + 1, 0);
mp.put(arr[i][0], mp.get(arr[i][0]) + 1);
mp.put(arr[i][1] + 1,
mp.get(arr[i][1] + 1) - 1);
}
ArrayList<Integer> range = new ArrayList<Integer>();
ArrayList<Integer> freq = new ArrayList<Integer>();
int prefixSum = 0;
for (Map.Entry<Integer, Integer> i :
mp.entrySet()) {
// Calculate the frequency of element
// using prefix sum technique.
prefixSum = prefixSum + i.getValue();
// Store the element of arr in range
range.add(i.getKey());
// Store its corresponding frequency
freq.add(prefixSum);
}
// Iterate over the query
for (Integer p : q) {
// Find the lower_bound of query p
int idx = lower_bound(range, p);
// If the lower_bound doesn't exist
if (idx >= 0 && idx < range.size()) {
// Check if element
// which we are searching
// exists in the range or not.
// If it doesn't exist then
// lower bound will return
// the next element which is
// just greater than p
if (range.get(idx) != p)
idx--;
if (idx >= 0)
result.add(freq.get(idx));
// If no such element exist
else
result.add(0);
}
// If idx is range size,
// it means all elements
// are smaller than p.
// So next smaller element will be
// at range.size() - 1
else {
result.add(freq.get(range.size() - 1));
}
}
// Return the final result
return result;
}
// Driver code
public static void main(String[] args)
{
int[][] arr
= { { 1, 5 }, { 3, 6 }, { 5, 7 }, { 12, 15 } };
int[] q = { 1, 3, 5, 13 };
ArrayList<Integer> result
= new ArrayList<Integer>();
// Function call
findTheOccurrence(arr, q, result);
for (Integer i : result)
System.out.print(i + " ");
}
}
// This code is contributed by phasing17
Python3
# Python3 code to implement the approach
import bisect
# Function to find the frequency
# of element in array arr
def findTheOccurrence(arr, q, result):
n = len(arr)
# Map to store the elements
# with their frequency
mp = {}
for i in arr:
if i[0] not in mp:
mp[i[0]] = 0
if (i[1] + 1) not in mp:
mp[i[1] + 1] = 0
mp[i[0]] += 1
mp[i[1] + 1] -= 1
range = []
freq = []
prefixSum = 0
for i in sorted(mp.keys()):
# Calculate the frequency of element
# using prefix sum technique.
prefixSum = prefixSum + mp[i]
# Store the element of arr in range
range.append(i)
# Store its corresponding frequency
freq.append(prefixSum)
# Iterate over the query
for p in q:
# Find the lower_bound of query p
idx = bisect.bisect_left(range, p)
# If the lower_bound doesn't exist
if (idx >= 0 and idx < len(range)):
# Check if element
# which we are searching
# exists in the range or not.
# If it doesn't exist then
# lower bound will return
# the next element which is
# just greater than p
if (range[idx] != p):
idx -= 1
if (idx >= 0):
result.append(freq[idx])
# If no such element exist
else:
result.append(0)
# If idx is range size,
# it means all elements
# are smaller than p.
# So next smaller element will be
# at range.size() - 1
else :
result.append(freq[len(range) - 1])
# Return the final result
return result
# Driver code
arr = [[ 1, 5 ], [ 3, 6 ], [ 5, 7 ], [ 12, 15 ] ]
q = [ 1, 3, 5, 13 ]
result = []
# Function call
result = findTheOccurrence(arr, q, result);
print(" ".join(list(map(str, result))))
# This code is contributed by phasing17
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
class GFG {
// This function returns the position
// of the leftmost array element that is
// greater than or equal to the key element
static int lower_bound(List<int> arr, int ele)
{
for (var i = 0; i < arr.Count; i++) {
if (arr[i] >= ele)
return i;
}
return arr.Count;
}
// Function to find the frequency
// of element in array arr
static List<int> findTheOccurrence(int[, ] arr, int[] q,
List<int> result)
{
// Map to store the elements
// with their frequency
Dictionary<int, int> mp
= new Dictionary<int, int>();
for (int i = 0; i < arr.GetLength(0); i++) {
if (!mp.ContainsKey(arr[i, 0]))
mp[arr[i, 0]] = 0;
if (!mp.ContainsKey(arr[i, 1] + 1))
mp[arr[i, 1] + 1] = 0;
mp[arr[i, 0]] += 1;
mp[arr[i, 1] + 1] -= 1;
}
List<int> range = new List<int>();
List<int> freq = new List<int>();
int prefixSum = 0;
var mpKeys = new List<int>(mp.Keys);
mpKeys.Sort();
foreach(var i in mpKeys)
{
// Calculate the frequency of element
// using prefix sum technique.
prefixSum = prefixSum + mp[i];
// Store the element of arr in range
range.Add(i);
// Store its corresponding frequency
freq.Add(prefixSum);
}
// Iterate over the query
foreach(var p in q)
{
// Find the lower_bound of query p
int idx = lower_bound(range, p);
// If the lower_bound doesn't exist
if (idx >= 0 && idx < range.Count) {
// Check if element
// which we are searching
// exists in the range or not.
// If it doesn't exist then
// lower bound will return
// the next element which is
// just greater than p
if (range[idx] != p)
idx--;
if (idx >= 0)
result.Add(freq[idx]);
// If no such element exist
else
result.Add(0);
}
// If idx is range size,
// it means all elements
// are smaller than p.
// So next smaller element will be
// at range.size() - 1
else {
result.Add(freq[range.Count - 1]);
}
}
// Return the final result
return result;
}
// Driver code
public static void Main(string[] args)
{
int[, ] arr
= { { 1, 5 }, { 3, 6 }, { 5, 7 }, { 12, 15 } };
int[] q = { 1, 3, 5, 13 };
List<int> result = new List<int>();
// Function call
findTheOccurrence(arr, q, result);
foreach(var i in result) Console.Write(i + " ");
}
}
// This code is contributed by phasing17
Javascript
// JavaScript code to implement the approach
//This function returns the position
//of the leftmost array element that is
//greater than or equal to the key element
function lower_bound(arr, ele)
{
for (var i = 0; i < arr.length; i++)
{
if (arr[i] >= ele)
return i;
}
return arr.length - 1;
}
// Function to find the frequency
// of element in array arr
function findTheOccurrence(arr, q, result)
{
let n = arr.length;
// Map to store the elements
// with their frequency
let mp = {};
for (var i of arr) {
if (!mp.hasOwnProperty(i[0]))
mp[i[0]] = 0;
if (!mp.hasOwnProperty(i[1] + 1))
mp[i[1] + 1] = 0;
mp[i[0]]++;
mp[i[1] + 1]--;
}
let range = [];
let freq = [];
let prefixSum = 0;
for (let [i, val] of Object.entries(mp)) {
// Calculate the frequency of element
// using prefix sum technique.
prefixSum = prefixSum + val;
// Store the element of arr in range
range.push(parseInt(i));
// Store its corresponding frequency
freq.push(prefixSum);
}
// Iterate over the query
for (var p of q) {
// Find the lower_bound of query p
let idx = lower_bound(range, p);
// If the lower_bound doesn't exist
if (idx >= 0 && idx < range.length) {
// Check if element
// which we are searching
// exists in the range or not.
// If it doesn't exist then
// lower bound will return
// the next element which is
// just greater than p
if (range[idx] != p)
idx--;
if (idx >= 0)
result.push(freq[idx]);
// If no such element exist
else
result.push(0);
}
// If idx is range size,
// it means all elements
// are smaller than p.
// So next smaller element will be
// at range.size() - 1
else {
result.push(freq[range.length - 1]);
}
}
// Return the final result
return result;
}
// Driver code
let arr = [[ 1, 5 ], [ 3, 6 ], [ 5, 7 ], [ 12, 15 ] ];
let q = [ 1, 3, 5, 13 ];
let result = [];
// Function call
result = findTheOccurrence(arr, q, result);
for (var i of result)
process.stdout.write(i + " ");
//This code is contributed by phasing17
Producción
1 2 3 1
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por harendrakumar123 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA