算法设计：整数流中的模式(运行整数)

本文概述

• C ++
• Java
• Python3
• C#

假定正在从数据流读取整数。找出模式 从第一个整数到最后一个整数, 到目前为止读取的所有元素的总数。

模式定义为出现最长时间的元素。如果两个或多个元素具有相同的最大频率, 则采用最后出现的那个。

例子：

输入：stream [] = {2, 7, 3, 2, 5}
输出：2 7 3 2 2
说明：
运行Stream的模式计算如下：
Mode({2})= 2
Mode({2, 7} )= 7
Mode({2, 7, 3})= 3
Mode({2, 7, 3, 2})= 2
Mode({2, 7, 3, 2, 2})= 2
输入：stream [] = {3, 5, 9, 9, 2, 3, 3, 4}
输出：3 5 9 9 9 3 3 3

方法：想法是使用哈希图 将元素映射到其频率。在逐一读取元素时, 将更新映射中元素的频率, 并且还将更新模式, 该模式将成为运行整数流的模式。

下面是上述方法的实现：

C ++

//C++ program to implement
//the above approach
#include<bits/stdc++.h>
using namespace std;
  
//Function that prints
//the Mode values
void findMode( int a[], int n)
{
      
     //Map used to mp integers
     //to its frequency
     map<int , int> mp; 
  
     //To store the maximum frequency
     int max = 0;
  
     //To store the element with
     //the maximum frequency
     int mode = 0;
      
     //Loop used to read the
     //elements one by one
     for ( int i = 0; i <n; i++) 
     {
          
         //Updates the frequency of
         //that element
         mp[a[i]]++;
      
         //Checks for maximum Number
         //of occurrence
         if (mp[a[i]]>= max) 
         {
      
             //Updates the maximum frequency
             max = mp[a[i]];
      
             //Updates the Mode
             mode = a[i];
         }
         cout <<mode <<" " ;
     }
}
      
//Driver Code
int main()
{
     int arr[] = { 2, 7, 3, 2, 5 };
     int n = sizeof (arr)/sizeof (arr[0]);
  
     //Function call
     findMode(arr, n);
  
     return 0;
} 
  
//This code is contributed by rutvik_56

Java

//Java implementation of the
//above approach
  
import java.util.*;
  
public class GFG {
  
     //Function that prints
     //the Mode values
     public static void findMode( int [] a, int n)
     {
         //Map used to map integers
         //to its frequency
         Map<Integer, Integer> map
             = new HashMap<>();
  
         //To store the maximum frequency
         int max = 0 ;
  
         //To store the element with
         //the maximum frequency
         int mode = 0 ;
  
         //Loop used to read the
         //elements one by one
         for ( int i = 0 ; i <n; i++) {
  
             //Updates the frequency of
             //that element
             map.put(a[i], map.getOrDefault(a[i], 0 ) + 1 );
  
             //Checks for maximum Number
             //of occurrence
             if (map.get(a[i])>= max) {
  
                 //Updates the maximum frequency
                 max = map.get(a[i]);
  
                 //Updates the Mode
                 mode = a[i];
             }
  
             System.out.print(mode);
             System.out.print( " " );
         }
     }
  
     //Driver Code
     public static void main(String[] args)
     {
         int arr[] = { 2 , 7 , 3 , 2 , 5 };
  
         int n = arr.length;
  
         //Function Call
         findMode(arr, n);
     }
}

Python3

# Python3 implementation of the 
# above approach
  
# Function that prints 
# the Mode values 
def findMode(a, n):
      
     # Map used to mp integers 
     # to its frequency 
     mp = {}
      
     # To store the maximum frequency 
     max = 0
      
     # To store the element with 
     # the maximum frequency 
     mode = 0
      
     # Loop used to read the 
     # elements one by one 
     for i in range (n):
         if a[i] in mp:
             mp[a[i]] + = 1
         else :
             mp[a[i]] = 1
          
         # Checks for maximum Number 
         # of occurrence     
         if (mp[a[i]]> = max ):
              
             # Updates the maximum 
             # frequency 
             max = mp[a[i]]
              
             # Updates the Mode 
             mode = a[i]
              
         print (mode, end = " " )
  
# Driver Code
arr = [ 2 , 7 , 3 , 2 , 5 ]
n = len (arr)
  
# Function call 
findMode(arr, n)
  
# This code is contributed by divyeshrabadiya07

C#

//C# implementation of the
//above approach
using System;
using System.Collections.Generic;
class GFG{
  
     //Function that prints
     //the Mode values
     public static void findMode( int [] a, int n)
     {
         //Map used to map integers
         //to its frequency
         Dictionary<int , int> map = new Dictionary<int , int>();
  
         //To store the maximum frequency
         int max = 0;
  
         //To store the element with
         //the maximum frequency
         int mode = 0;
  
         //Loop used to read the
         //elements one by one
         for ( int i = 0; i <n; i++) 
         {
          
             //Updates the frequency of
             //that element
             if (map.ContainsKey(a[i])) 
             {
                 map[a[i]] = map[a[i]] + 1;
             }
             else
             {
                 map.Add(a[i], 1);
             }
  
             //Checks for maximum Number
             //of occurrence
             if (map[a[i]]>= max) 
             {
  
                 //Updates the maximum frequency
                 max = map[a[i]];
  
                 //Updates the Mode
                 mode = a[i];
             }
             Console.Write(mode);
             Console.Write( " " );
         }
     }
  
     //Driver Code
     public static void Main(String[] args)
     {
         int [] arr = {2, 7, 3, 2, 5};
         int n = arr.Length;
  
         //Function Call
         findMode(arr, n);
     }
}
  
//This code is contributed by Amit Katiyar

输出如下：

2 7 3 2 2

性能分析：

• 时间复杂度：O(n)
• 辅助空间：O(n)

---