Dados N rangos de LR. La tarea es imprimir el número que ocurre el número máximo de veces en los rangos dados.
Nota: 1 <= L <= R <= 10 6
Ejemplos:
Entrada: rango[] = { {1, 6}, {2, 3}, {2, 5}, {3, 8} }
Salida: 3
1 ocurre en 1 rango {1, 6}
2 ocurre 3 en 3 rango {1, 6}, {2, 3}, {2, 5}
3 ocurren 4 en 4 rango {1, 6}, {2, 3}, {2, 5}, {3, 8}
4 ocurren 3 en 3 rango {1, 6}, {2, 5}, {3, 8}
5 ocurren 3 en 3 rango {1, 6}, {2, 5}, {3, 8}
6 ocurren 2 en 2 rango {1 , 6}, {3, 8}
7 ocurre 1 en 1 rango {3, 8}
8 ocurre 1 en 1 rango {3, 8}
Entrada: range[] = { {1, 4}, {1, 9}, {1, 2}};
Salida: 1
Enfoque: El enfoque es similar al Número máximo ocurrido en n rangos . Lo único que es diferente es encontrar el límite inferior y superior de los rangos. Para que no haya necesidad de pasar de 1 a MAX.
A continuación se muestra el algoritmo paso a paso para resolver este problema:
- Inicialice una array de frecuencia con 0, deje que el tamaño de la array sea 10 ^ 6 ya que este es el máximo posible.
- Aumente la frecuencia [l] en 1 , para cada índice inicial del rango dado.
- Disminuya la frecuencia [r+1] en 1 para cada índice final del rango dado.
- Iterar desde el mínimo L hasta el máximo R y sumar las frecuencias por freq[i] += freq[i-1] .
- El índice con el valor máximo de freq[i] será la respuesta.
- Guarde el índice y devuélvalo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check the most occurring
// element in given range
#include <bits/stdc++.h>
using namespace std;
// Function that returns the maximum element.
int maxOccurring(int range[][2], int n)
{
// freq array to store the frequency
int freq[(int)(1e6 + 2)] = { 0 };
int first = 0, last = 0;
// iterate and mark the hash array
for (int i = 0; i < n; i++) {
int l = range[i][0];
int r = range[i][1];
// increase the hash array by 1 at L
freq[l] += 1;
// Decrease the hash array by 1 at R
freq[r + 1] -= 1;
first = min(first, l);
last = max(last, r);
}
// stores the maximum frequency
int maximum = 0;
int element = 0;
// check for the most occurring element
for (int i = first; i <= last; i++) {
// increase the frequency
freq[i] = freq[i - 1] + freq[i];
// check if is more than the previous one
if (freq[i] > maximum) {
maximum = freq[i];
element = i;
}
}
return element;
}
// Driver code
int main()
{
int range[][2] = { { 1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 8 } };
int n = 4;
// function call
cout << maxOccurring(range, n);
return 0;
}
Java
// Java program to check the most occurring
// element in given range
class GFG
{
// Function that returns the maximum element.
static int maxOccurring(int range[][], int n)
{
// freq array to store the frequency
int []freq = new int[(int)(1e6 + 2)];
int first = 0, last = 0;
// iterate and mark the hash array
for (int i = 0; i < n; i++)
{
int l = range[i][0];
int r = range[i][1];
// increase the hash array by 1 at L
freq[l] += 1;
// Decrease the hash array by 1 at R
freq[r + 1] -= 1;
first = Math.min(first, l);
last = Math.max(last, r);
}
// stores the maximum frequency
int maximum = 0;
int element = 0;
// check for the most occurring element
for (int i = first+1; i <= last; i++)
{
// increase the frequency
freq[i] = freq[i - 1] + freq[i];
// check if is more than the previous one
if (freq[i] > maximum)
{
maximum = freq[i];
element = i;
}
}
return element;
}
// Driver code
public static void main(String[] args)
{
int range[][] = { { 1, 6 }, { 2, 3 },
{ 2, 5 }, { 3, 8 } };
int n = 4;
// function call
System.out.println(maxOccurring(range, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to check the most # occurring element in given range # Function that returns the # maximum element. def maxOccurring(range1, n): # freq array to store the frequency freq = [0] * 1000002; first = 0; last = 0; # iterate and mark the hash array for i in range(n): l = range1[i][0]; r = range1[i][1]; # increase the hash array by 1 at L freq[l] += 1; # Decrease the hash array by 1 at R freq[r + 1] -= 1; first = min(first, l); last = max(last, r); # stores the maximum frequency maximum = 0; element = 0; # check for the most occurring element for i in range(first, last + 1): # increase the frequency freq[i] = freq[i - 1] + freq[i]; # check if is more than the # previous one if(freq[i] > maximum): maximum = freq[i]; element = i; return element; # Driver code range1= [[ 1, 6 ], [ 2, 3 ], [ 2, 5 ], [ 3, 8 ]]; n = 4; # function call print(maxOccurring(range1, n)); # This code is contributed by mits
C#
// C# program to check the most occurring
// element in given range
using System;
class GFG
{
// Function that returns the maximum element.
static int maxOccurring(int [,]range, int n)
{
// freq array to store the frequency
int []freq = new int[(int)(1e6 + 2)];
int first = 0, last = 0;
// iterate and mark the hash array
for (int i = 0; i < n; i++)
{
int l = range[i, 0];
int r = range[i, 1];
// increase the hash array by 1 at L
freq[l] += 1;
// Decrease the hash array by 1 at R
freq[r + 1] -= 1;
first = Math.Min(first, l);
last = Math.Max(last, r);
}
// stores the maximum frequency
int maximum = 0;
int element = 0;
// check for the most occurring element
for (int i = first + 1; i <= last; i++)
{
// increase the frequency
freq[i] = freq[i - 1] + freq[i];
// check if is more than the previous one
if (freq[i] > maximum)
{
maximum = freq[i];
element = i;
}
}
return element;
}
// Driver code
public static void Main(String[] args)
{
int [,]range = {{ 1, 6 }, { 2, 3 },
{ 2, 5 }, { 3, 8 }};
int n = 4;
// function call
Console.WriteLine(maxOccurring(range, n));
}
}
// This code is contributed by Princi Singh
PHP
<?php
// PHP program to check the most occurring
// element in given range
// Function that returns the maximum element.
function maxOccurring(&$range, $n)
{
// freq array to store the frequency
$freq = array(0, 1000002, NULL);
$first = 0;
$last = 0;
// iterate and mark the hash array
for ($i = 0; $i < $n; $i++)
{
$l = $range[$i][0];
$r = $range[$i][1];
// increase the hash array
// by 1 at L
$freq[$l] += 1;
// Decrease the hash array
// by 1 at R
$freq[$r + 1] -= 1;
$first = min($first, $l);
$last = max($last, $r);
}
// stores the maximum frequency
$maximum = 0;
$element = 0;
// check for the most occurring element
for ($i = $first; $i <= $last; $i++)
{
// increase the frequency
$freq[$i] = $freq[$i - 1] + $freq[$i];
// check if is more than the
// previous one
if ($freq[$i] > $maximum)
{
$maximum = $freq[$i];
$element = $i;
}
}
return $element;
}
// Driver code
$range = array(array( 1, 6 ),
array( 2, 3 ),
array( 2, 5 ),
array( 3, 8 ));
$n = 4;
// function call
echo maxOccurring($range, $n);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to check the most occurring
// element in given range
// Function that returns the maximum element.
function maxOccurring(range , n)
{
// freq array to store the frequency
var freq = Array(parseInt(1e6 + 2)).fill(0);
var first = 0, last = 0;
// iterate and mark the hash array
for (i = 0; i < n; i++) {
var l = range[i][0];
var r = range[i][1];
// increase the hash array by 1 at L
freq[l] += 1;
// Decrease the hash array by 1 at R
freq[r + 1] -= 1;
first = Math.min(first, l);
last = Math.max(last, r);
}
// stores the maximum frequency
var maximum = 0;
var element = 0;
// check for the most occurring element
for (i = first + 1; i <= last; i++) {
// increase the frequency
freq[i] = freq[i - 1] + freq[i];
// check if is more than the previous one
if (freq[i] > maximum) {
maximum = freq[i];
element = i;
}
}
return element;
}
// Driver code
var range = [ [ 1, 6 ], [ 2, 3 ],
[ 2, 5 ], [ 3, 8 ] ];
var n = 4;
// function call
document.write(maxOccurring(range, n));
// This code contributed by gauravrajput1
</script>
Producción:
3
Complejidad Temporal : O(N + M), donde M es el valor máximo entre los rangos.
Espacio auxiliar : O(10 6 ), ya que estamos usando espacio adicional para la array de frecuencias .
Nota: Si los valores de L y T son del orden de 10 8 , el método anterior no funcionará porque habrá un error de memoria. Necesitamos un enfoque diferente pero similar para estos límites. Puedes pensar en términos de hashing.