n个范围内出现的最大整数-yiteyi-C++库

鉴于 N 表格的范围 L 和 R ，任务是找到所有范围内出现的最大整数。如果存在多个这样的整数，请打印最小的一个。 0<=L _我 R _我 < 1000000. 例如：

null

Input : L₁ = 1 R₁ = 15        L₂ = 4 R₂ = 8        L₃ = 3 R₃ = 5        L₄ = 1 R₄ = 4Output : 4Input : L₁ = 1 R₁ = 15        L₂ = 5 R₂ = 8        L₃ = 9 R₃ = 12        L₄ = 13 R₄ = 20        L₅ = 21 R₅ = 30Output : 5Numbers having maximum occurrence i.e 2  are 5, 6,7, 8, 9, 10, 11, 12, 13, 14, 15. The smallest numberamong all are 5.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们穿过所有的山脉。然后，我们计算每个范围的频率，制作一个哈希表或哈希映射，存储每个项目。然后你穿过其他范围，增加每一项的频率。频率最高的项目是我们的答案。但是这个解决方案需要时间，比如说有N个范围，如果M是任何范围内元素的最大数量，那么需要O（N*M）时间。哈希表的插入、搜索和删除的时间复杂度为O（1）。因此，您可以插入哈希表中的每一项，并将其频率设置为O（1）。

有效率的方法：-时间复杂度O（N+max）

如果范围是固定的，比如（0<=Li，Ri<1000000），我们可以在更好的时间复杂度下实现这一点。这里的诀窍是我们不想旅行每一个范围的每一个元素。我们只想遍历所有范围，我们想使用前缀和技术来解决这个问题。

我们创建一个vector/Arraylist/Array。向量中的所有值都用零初始化（使用向量或数组列表来避免C++中的MeSET）的额外行。在java中填充（）。所以我们要做的是在每个范围内循环，并标记每个范围的开头。我们只是这么做 arr[L[i]]++ .我们还通过从中减去一来标记这个范围的结束 arr[R[i+1]] .

正如我之前所讨论的，我们将每个范围的开始标记为一。

所以如果我做一个前缀和，如果我标记开始，所有的值都会在这个元素之后增加一。现在我们只想增加到数组的末尾。我们不想增加其他元素。

比如说，

L[]={1,2,3}，R[]={3,5,7}

1.对于这条线arr[L[i]++数组变成{0,1,1,0,0,0,0，…}

2.对于这条线arr[R[i+1]——数组变成{0,1,1,1，-1,0，-1,0，-1，…}

3.当我们进行前缀求和时，数组变成{0,1,2,3,2,2,1,1,0…}

当我们使用前缀sum时，我们将使（1）之后的元素之和增加1，因为我标记了开头。现在我不希望这个增量发生在（3）之后的元素上。所以如果有一个范围1，2，3，1，2，3的值应该只增加1，或者它们的频率应该增加1。

这就是为什么我们降低了arr[R[i+1]]的值。所以这个范围结束后的元素的值减去1。这就是当我要做前缀时，我们如何消除增加值的影响。

所以，当我要做前缀时，我只需要增加范围后的每个值，因为我只想在范围内增加。这就是这个算法的想法。

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>                       

输出：

时间复杂性： O（n+最大值）

练习： 尝试0<=L _我 R _我 <= 1000000000. （提示：使用stl映射）。 相关文章： m范围增量运算后数组中的最大值本文由凯尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END