算法设计（求n范围内出现的最大整数）

本文概述

建议：在继续解决方案之前, 请先在"实践"上解决它。
C ++
Java
Python3
C#
的PHP

给定
?
形式范围
大号
和
[R
, 任务是查找所有范围内出现的最大整数。如果存在多个这样的整数, 请打印最小的整数。
0 < =大
一世
, R
一世
< 1000000。
例子：

Input : L1 = 1 R1 = 15L2 = 4 R2 = 8L3 = 3 R3 = 5L3 = 1 R3 = 4Output : 4Input : L1 = 1 R1 = 15L2 = 5 R2 = 8L3 = 9 R3 = 12L4 = 13 R4 = 20L5 = 21 R5 = 30Output : 5Numbers having maximum occurrence i.e 2are 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. The smallest numberamong all are 5.

推荐：请在"实践首先, 在继续解决方案之前。
【算法设计（求n范围内出现的最大整数）】一种简单的解决方案是使用哈希表存储所有数字的计数。我们从L遍历每个间隔一世到R一世以及每个间隔中出现的所有数字的增量计数。最后, 我们遍历哈希表以找到具有最大计数的数字。此解决方案的时间复杂度为O(n * MAX_INTERVAL), 其中MAX_INTERVAL是一个间隔中的最大元素数。
An有效的解决方案需要线性时间。我们创建一个大小为1000000的数组arr [](给定一个间隔的最大值的限制)。这个想法是给每个L加+1一世索引和-1对应的R一世arr []中的索引。之后, 找到数组的前缀和。在L加+1一世显示ith范围的起点, 加-1显示ith范围的终点。最后, 我们返回具有最大前缀和的数组索引
解决问题的算法：

将数组arr []初始化为0。
对于每个范围i, 在L处加+1一世索引和-1在R一世的数组。
找到数组的前缀和, 并找到具有最大前缀和的最小索引。

以下是此方法的实现：
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) { // Initalising all element of array to 0. int arr[MAX]; memset (arr, 0, sizeof arr); // Adding +1 at Li index and substracting 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) { // Initalising all element of array to 0. int [] arr = new int [MAX]; // Adding +1 at Li index and // substracting 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):# Initalising all element of array to 0. arr = [ 0 for i in range ( MAX )]# Adding +1 at Li index and substracting 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# 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) { // Initalising all element of array to 0. int [] arr = new int [MAX]; // Adding +1 at Li index and // substracting 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 ) {// Initalising 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 ?>

输出如下：