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

2021年3月11日16:49:11 发表评论 786 次浏览

本文概述

给定

ñ

形式范围

大号

和

[R

, 任务是查找所有范围内出现的最大整数。如果存在多个这样的整数, 请打印最小的整数。

0 <=大

一世

, R

一世

<1000000。

例子 ：

Input : L1 = 1 R1 = 15
        L2 = 4 R2 = 8
        L3 = 3 R3 = 5
        L3 = 1 R3 = 4
Output : 4

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

推荐：请在"实践首先, 在继续解决方案之前。

一种简单的解决方案是使用哈希表存储所有数字的计数。我们从L遍历每个间隔一世到R一世以及每个间隔中出现的所有数字的增量计数。最后, 我们遍历哈希表以找到具有最大计数的数字。此解决方案的时间复杂度为O(n * MAX_INTERVAL), 其中MAX_INTERVAL是一个间隔中的最大元素数。

An有效的解决方案需要线性时间。我们创建一个大小为1000000的数组arr [](给定一个间隔的最大值的限制)。这个想法是给每个L加+1一世索引和-1对应的R一世arr []中的索引。之后, 找到数组的前缀和。在L加+1一世显示ith范围的起点, 加-1显示ith范围的终点。最后, 我们返回具有最大前缀和的数组索引

解决问题的算法：

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

以下是此方法的实现：

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#

// 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
?>

输出如下：

4

时间复杂度：O(n +最大)

行使：尝试0 <= L一世, R一世<=1000000000。(提示：使用stl映射)。

相关文章：m个范围增量操作后数组中的最大值

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: