算法（如何实现求n范围内出现的最大整数-S2） _数据结构

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#
的PHP

给定N范围的L-R。任务是打印在给定范围内出现最大次数的数字。
注意：1 < = L < = R < = 106
例子：

输入：range [] = {{1, 6}, {2, 3}, {2, 5}, {3, 8}}输出：3 1在1范围内发生{1, 6} 2在3范围内发生3 {1, 6}, {2, 3}, {2, 5} 3在4范围内出现4 {1, 6}, {2, 3}, {2, 5}, {3, 8} 4在3中出现3范围{1, 6}, {2, 5}, {3, 8} 5在3范围内出现3 {1, 6}, {2, 5}, {3, 8} 6在2范围内出现2 , 6}, {3, 8} 7在1范围内出现1 {3, 8} 8在1范围内出现1 {3, 8}输入：range [] = {{1, 4}, {1, 9}, {1, 2}}; 输出1

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。方法：该方法类似于n范围内出现的最大整数。唯一不同的是找到范围的下限和上限。这样就无需从1遍历到MAX。
以下是解决此问题的分步算法：

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

下面是上述方法的实现：
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# 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 ?>

输出如下：