Dados n rangos de la forma L y R , la tarea es encontrar el entero máximo ocurrido en todos los rangos. Si existe más de uno de estos enteros, imprima el más pequeño.
0 <= L yo , R yo < 1000000.
Ejemplos:
Input : L1 = 1 R1 = 15
L2 = 4 R2 = 8
L3 = 3 R3 = 5
L4 = 1 R4 = 4
Output : 4
Input : L1 = 1 R1 = 15
L2 = 5 R2 = 8
L3 = 9 R3 = 12
L4 = 13 R4 = 20
L5 = 21 R5 = 30
Output : 5
Numbers having maximum occurrence i.e 2 are 5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15. The smallest number
among all are 5.
Atravesamos todos los rangos. Luego, para cada rango, contamos las frecuencias, hacemos una tabla hash o un mapa hash donde almacenamos cada elemento. Luego viaja a través de otros rangos e incrementa la frecuencia de cada elemento. El elemento con la frecuencia más alta es nuestra respuesta. Pero esta solución requiere tiempo, digamos que hay N rangos y si M es el número máximo de elementos en cualquiera de los rangos, entonces tomará O (N * M) tiempo. La tabla hash tiene la complejidad temporal de insertar, buscar y eliminar como O(1). Entonces puede insertar cada elemento en la tabla hash y su frecuencia en O (1).
Enfoque eficiente : – Complejidad de tiempo O (N + max)
Podemos hacer esto con una mejor complejidad de tiempo si los rangos son fijos, digamos (0 <= Li, Ri < 1000000). El truco aquí es que no queremos recorrer cada elemento de cada rango. Solo queremos viajar a través de todos los rangos y queremos usar la técnica de la suma de prefijos para resolver este problema.
Creamos un vector/Arraylist/Array. Todos los valores en el vector se inicializan en cero (use el vector o ArrayList para evitar esa línea extra de .memset() en c++ o .fill() en java). Entonces, lo que hacemos es recorrer cada rango y marcar la presencia del comienzo de cada rango. Simplemente hacemos esto arr[L[i]]++ . También marcamos el final de este rango restando uno de arr[R[i]+1] .
Como mencioné anteriormente, Marcamos la presencia del comienzo de cada rango como uno.
Entonces, si hago una suma de prefijos y marco el comienzo, todos los valores se incrementarán en uno después de este elemento. Ahora queremos incrementar solo hasta el final de la array. No queremos incrementar otros elementos.
Digamos,
L[] = {1, 2, 3} , R[] = {3, 5 , 7}
1. para esta línea arr[L[i]]++ la array se convierte en {0,1,1,1,0,0,0,0,……}
2. para esta línea arr[R[i]+1]– la array se convierte en {0,1,1,1,-1, 0, -1, 0,-1,……}
3. cuando hacemos suma de prefijos, la array se convierte en {0,1,2,3,2,2,1,1,0…}
Cuando hagamos la suma de prefijos, tendremos la suma de los elementos después de (1) incrementada en uno porque marqué el comienzo. Ahora no quiero que este incremento le suceda a los elementos después de (3). Entonces, si hay un rango uno, dos, tres, los valores de uno, dos, tres solo deben incrementarse en uno o su frecuencia debe incrementarse en uno.
Por eso disminuimos el valor de arr[R[i]+1]. De modo que los elementos después del final de este rango tengan valores menos uno restado. Así anulamos el impacto de incrementar el valor cuando voy a hacer el prefijo.
Entonces, cuando voy a hacer el prefijo, simplemente voy a incrementar cada valor después del rango, ya que quiero incrementar solo en el rango. Esa es la idea de este algoritmo.
Implementación:
C++
// C++ program to find maximum occurred element in
// given N ranges.
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
// Return the maximum occurred element in all ranges.
int maximumOccurredElement(int L[], int R[], int n)
{
// Initialising all element of array to 0.
int arr[MAX];
memset(arr, 0, sizeof arr);
// Adding +1 at Li index and subtracting 1
// at Ri index.
int maxi=-1;
for (int i = 0; i < n; i++) {
arr[L[i]] += 1;
arr[R[i] + 1] -= 1;
if(R[i]>maxi){
maxi=R[i];
}
}
// Finding prefix sum and index having maximum
// prefix sum.
int msum = arr[0],ind;
for (int i = 1; i < maxi+1; i++) {
arr[i] += arr[i - 1];
if (msum < arr[i]) {
msum = arr[i];
ind = i;
}
}
return ind;
}
// Driven Program
int main()
{
int L[] = { 1, 4, 9, 13, 21 };
int R[] = { 15, 8, 12, 20, 30 };
int n = sizeof(L) / sizeof(L[0]);
cout << maximumOccurredElement(L, R, n) << endl;
return 0;
}
Java
// Java program to find maximum occurred
// element in given N ranges.
import java.io.*;
class GFG {
static int MAX = 1000000;
// Return the maximum occurred element in all ranges.
static int maximumOccurredElement(int[] L, int[] R, int n)
{
// Initialising all element of array to 0.
int[] arr = new int[MAX];
// Adding +1 at Li index and
// subtracting 1 at Ri index.
int maxi=-1;
for (int i = 0; i < n; i++) {
arr[L[i]] += 1;
arr[R[i] + 1] -= 1;
if(R[i]>maxi){
maxi=R[i];
}
}
// Finding prefix sum and index
// having maximum prefix sum.
int msum = arr[0];
int ind = 0;
for (int i = 1; i < maxi+1; i++) {
arr[i] += arr[i - 1];
if (msum < arr[i]) {
msum = arr[i];
ind = i;
}
}
return ind;
}
// Driver program
static public void main(String[] args)
{
int[] L = { 1, 4, 9, 13, 21 };
int[] R = { 15, 8, 12, 20, 30 };
int n = L.length;
System.out.println(maximumOccurredElement(L, R, n));
}
}
// This code is contributed by vt_m.
Python3
# Python 3 program to find maximum occurred # element in given N ranges. MAX = 1000000 # Return the maximum occurred element # in all ranges. def maximumOccurredElement(L, R, n): # Initialising all element of array to 0. arr = [0 for i in range(MAX)] # Adding +1 at Li index and subtracting 1 # at Ri index. for i in range(0, n, 1): arr[L[i]] += 1 arr[R[i] + 1] -= 1 # Finding prefix sum and index # having maximum prefix sum. msum = arr[0] for i in range(1, MAX, 1): arr[i] += arr[i - 1] if (msum < arr[i]): msum = arr[i] ind = i return ind # Driver Code if __name__ == '__main__': L = [1, 4, 9, 13, 21] R = [15, 8, 12, 20, 30] n = len(L) print(maximumOccurredElement(L, R, n)) # This code is contributed by # Sanjit_Prasad
C#
// C# program to find maximum
// occurred element in given N ranges.
using System;
class GFG {
static int MAX = 1000000;
// Return the maximum occurred element in all ranges.
static int maximumOccurredElement(int[] L, int[] R, int n)
{
// Initialising all element of array to 0.
int[] arr = new int[MAX];
// Adding +1 at Li index and
// subtracting 1 at Ri index.
for (int i = 0; i < n; i++) {
arr[L[i]] += 1;
arr[R[i] + 1] -= 1;
}
// Finding prefix sum and index
// having maximum prefix sum.
int msum = arr[0];
int ind = 0;
for (int i = 1; i < MAX; i++) {
arr[i] += arr[i - 1];
if (msum < arr[i]) {
msum = arr[i];
ind = i;
}
}
return ind;
}
// Driver program
static public void Main()
{
int[] L = { 1, 4, 9, 13, 21 };
int[] R = { 15, 8, 12, 20, 30 };
int n = L.Length;
Console.WriteLine(maximumOccurredElement(L, R, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find maximum occurred
// element in given N ranges.
$MAX = 1000000;
// Return the maximum occurred element
// in all ranges.
function maximumOccurredElement($L, $R, $n)
{
// Initialising all element
// of array to 0.
$arr = array();
for($i = 0; $i < $n; $i++)
{
$arr[] = "0";
}
// Adding +1 at Li index and subtracting 1
// at Ri index.
for ($i = 0; $i < $n; $i++)
{
$arr[$L[$i]] += 1;
$arr[$R[$i] + 1] -= 1;
}
// Finding prefix sum and index
// having maximum prefix sum.
$msum = $arr[0];
for ($i = 1; $i <$n; $i++)
{
$arr[$i] += $arr[$i - 1];
if ($msum < $arr[$i])
{
$msum = $arr[$i];
$ind = $i;
}
}
return $ind;
}
// Driver Code
$L = array(1, 4, 9, 13, 21);
$R = array(15, 8, 12, 20, 30);
$n = count($L);
echo maximumOccurredElement($L, $R, $n);
// This code is contributed by
// Srathore
?>
Javascript
<script>
// JavaScript program to find maximum
// occurred element in given N ranges.
let MAX = 1000000;
// Return the maximum occurred element in all ranges.
function maximumOccurredElement(L, R, n)
{
// Initialising all element of array to 0.
let arr = new Array(MAX);
arr.fill(0);
// Adding +1 at Li index and
// subtracting 1 at Ri index.
for (let i = 0; i < n; i++) {
arr[L[i]] += 1;
arr[R[i] + 1] -= 1;
}
// Finding prefix sum and index
// having maximum prefix sum.
let msum = arr[0];
let ind = 0;
for (let i = 1; i < MAX; i++) {
arr[i] += arr[i - 1];
if (msum < arr[i]) {
msum = arr[i];
ind = i;
}
}
return ind;
}
let L = [ 1, 4, 9, 13, 21 ];
let R = [ 15, 8, 12, 20, 30 ];
let n = L.length;
document.write(maximumOccurredElement(L, R, n));
</script>
4
Complejidad temporal: O(n + MAX)
Ejercicio: Pruebe con 0 <= L i , R i <= 1000000000. (Sugerencia: use el mapa stl).
Artículo relacionado: valor máximo en una array después de m operaciones de incremento de rango
Este artículo es una contribución de KaaL-EL . 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