# 算法：如何实现求n范围内出现的最大整数-S2

2021年3月18日15:27:09 发表评论 340 次浏览

## 推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

1. 用0初始化一个freq数组, 让数组的大小为10 ^ 6, 因为这是最大可能的值。
2. 增加freq [l]乘1, 对于给定范围的每个起始索引。
3. 减少freq [r + 1]减1给定范围的每个结束索引。
4. 从最小L迭代到最大R, 然后将频率相加freq [i] + = freq [i-1].
5. 最大值为freq [i]的索引就是答案。
6. 存储索引并返回它。

## 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
?>``````

``3``