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

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

本文概述

给定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。

以下是解决此问题的分步算法：

  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

注意：如果值L和T的数量级为108则上述方法将无效, 因为会出现内存错误。对于这些限制, 我们需要一种不同但相似的方法。你可能会考虑哈希。

木子山

发表评论

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