Longitud del subarreglo más pequeño que consta de todas las ocurrencias de todos los elementos de ocurrencia máxima

Dado un arreglo arr[] de tamaño N , la tarea es encontrar la longitud del subarreglo más pequeño que consta de todas las ocurrencias de los elementos que ocurren con el máximo Ejemplos:

Entrada: arr[] = {1, 2, 1, 3, 2}
Salida: 5
Explicación: Los elementos con frecuencia máxima (=2) son 1 y 2. 
Por lo tanto, la longitud del subarreglo más pequeño que consta de todas las ocurrencias de 1 y 2 es 5, es decir, {1, 2, 1, 3, 2}

Entrada: arr[] = {1, 2, 5, 1, 5, 5}
Salida: 4

Enfoque: la tarea se puede resolver haciendo un seguimiento de la primera y la última ocurrencia de los elementos máximos que ocurren. La longitud del subarreglo más pequeño sería la diferencia entre el máximo de las últimas ocurrencias y el mínimo de las primeras ocurrencias. 
Siga los pasos a continuación para resolver el problema:

• Crear un mapa , para almacenar las frecuencias de los elementos .
• Encuentre los elementos con la frecuencia máxima y almacene su primera y última aparición.
• Finalmente, devuelva la diferencia entre el máximo de las últimas ocurrencias y el mínimo de las primeras ocurrencias

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of smallest
// subarray consisting of all the occurrences
// of maximum occurring elements
int get(int arr[], int n)
{
    // Stores the frequencies
    unordered_map<int, int> occ;
 
    // Stores the maximum frequency
    int mx = -1;
 
    for (int i = 0; i < n; i++) {
        occ[arr[i]]++;
        mx = max(mx, occ[arr[i]]);
    }
 
    // Stores the maximum occurring elements
    unordered_map<int, int> chk;
 
    for (auto x : occ) {
        if (x.second == mx)
            chk[x.first]++;
    }
 
    // Stores the minimum of first occurrences
    // and maximum of last occurrences
    // of all the maximum occurring elements
    int fr = INT_MAX, sc = INT_MIN;
 
    for (int i = 0; i < n; i++) {
 
        // Maximum occurring element
        if (chk.find(arr[i]) != chk.end()) {
            fr = min(fr, i);
            sc = max(sc, i);
        }
    }
 
    return sc - fr + 1;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 5, 1, 5, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
     
    cout << get(arr, n);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
  // Function to find the length of smallest
  // subarray consisting of all the occurrences
  // of maximum occurring elements
  static int get(int arr[], int n)
  {
 
    // Stores the frequencies
    HashMap<Integer,Integer> occ = new HashMap<Integer,Integer>();
 
    // Stores the maximum frequency
    int mx = -1;
 
    for (int i = 0; i < n; i++) {
      if(occ.containsKey(arr[i])){
        occ.put(arr[i], occ.get(arr[i])+1);
      }
      else{
        occ.put(arr[i], 1);
      }
      mx = Math.max(mx, occ.get(arr[i]));
    }
 
    // Stores the maximum occurring elements
    HashMap<Integer,Integer> chk= new HashMap<Integer,Integer>();
    for (Map.Entry<Integer,Integer> x : occ.entrySet()) {
      if (x.getValue() == mx)
        if(chk.containsKey(x.getKey())){
          chk.put(x.getKey(), chk.get(x.getKey())+1);
        }
      else{
        chk.put(x.getKey(), 1);
      }
    }
 
    // Stores the minimum of first occurrences
    // and maximum of last occurrences
    // of all the maximum occurring elements
    int fr = Integer.MAX_VALUE, sc = Integer.MIN_VALUE;
 
    for (int i = 0; i < n; i++) {
 
      // Maximum occurring element
      if (chk.containsKey(arr[i])) {
        fr = Math.min(fr, i);
        sc = Math.max(sc, i);
      }
    }
 
    return sc - fr + 1;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int arr[] = { 1, 2, 5, 1, 5, 5 };
    int n = arr.length;
 
    System.out.print(get(arr, n));
  }
}
 
// This code is contributed by shikhasingrajput

# Python 3 program for the above approach
import sys
from collections import defaultdict
 
# Function to find the length of smallest
# subarray consisting of all the occurrences
# of maximum occurring elements
def get(arr,  n):
 
    # Stores the frequencies
    occ = defaultdict(int)
 
    # Stores the maximum frequency
    mx = -1
 
    for i in range(n):
 
        occ[arr[i]] += 1
        mx = max(mx, occ[arr[i]])
 
    # Stores the maximum occurring elements
    chk = defaultdict(int)
 
    for x in occ:
        if (occ[x] == mx):
            chk[x] += 1
 
    # Stores the minimum of first occurrences
    # and maximum of last occurrences
    # of all the maximum occurring elements
    fr = sys.maxsize
    sc = -sys.maxsize
 
    for i in range(n):
 
        # Maximum occurring element
        if (arr[i] in chk):
            fr = min(fr, i)
            sc = max(sc, i)
 
    return sc - fr + 1
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 2, 5, 1, 5, 5]
    n = len(arr)
 
    print(get(arr, n))
 
    # This code is contributed by ukasp.

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
     
  // Function to find the length of smallest
  // subarray consisting of all the occurrences
  // of maximum occurring elements
  static int get(int []arr, int n)
  {
 
    // Stores the frequencies
    Dictionary<int, int> occ =
          new Dictionary<int, int>();
 
    // Stores the maximum frequency
    int mx = -1;
 
    for (int i = 0; i < n; i++) {
      if (occ.ContainsKey(arr[i]))
      {
        occ[arr[i]] = occ[arr[i]] + 1;
      }
      else
      {
        occ.Add(arr[i], 1);
      }
      mx = Math.Max(mx, occ[arr[i]]);
    }
    // Stores the maximum occurring elements
    Dictionary<int, int> chk =
          new Dictionary<int, int>();
           
    foreach (KeyValuePair<int, int> x in occ){
      if (x.Value == mx){
        if(chk.ContainsKey(x.Key)){
          chk[x.Key] = chk[x.Key] + 1;
        }
        else{
          chk.Add(x.Key, 1);
        }
      }
    }
 
    // Stores the minimum of first occurrences
    // and maximum of last occurrences
    // of all the maximum occurring elements
    int fr = Int32.MaxValue, sc = Int32.MinValue;
 
    for (int i = 0; i < n; i++) {
 
      // Maximum occurring element
      if (chk.ContainsKey(arr[i])) {
        fr = Math.Min(fr, i);
        sc = Math.Max(sc, i);
      }
    }
 
    return sc - fr + 1;
  }
 
  // Driver Code
  public static void Main()
  {
    int []arr = { 1, 2, 5, 1, 5, 5 };
    int n = arr.Length;
 
    Console.Write(get(arr, n));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to find the length of smallest
       // subarray consisting of all the occurrences
       // of maximum occurring elements
       function get(arr, n)
       {
        
           // Stores the frequencies
           let occ = new Map();
 
           // Stores the maximum frequency
           let mx = -1;
 
           for (let i = 0; i < n; i++) {
 
 
               if (occ.has(arr[i])) {
                   occ.set(arr[i], occ.get(arr[i]) + 1)
               }
               else {
                   occ.set(arr[i], 1)
               }
               mx = Math.max(mx, occ.get(arr[i]));
           }
 
           // Stores the maximum occurring elements
           let chk = new Map();
 
           for (let [key, val] of occ) {
               if (val == mx)
 
                   chk.set(key, chk.get(key) + 1)
           }
 
           // Stores the minimum of first occurrences
           // and maximum of last occurrences
           // of all the maximum occurring elements
           let fr = Number.MAX_VALUE, sc = Number.MIN_VALUE;
 
           for (let i = 0; i < n; i++) {
 
               // Maximum occurring element
               if (chk.has(arr[i])) {
                   fr = Math.min(fr, i);
                   sc = Math.max(sc, i);
               }
           }
 
           return sc - fr + 1;
       }
 
       // Driver Code
       let arr = [1, 2, 5, 1, 5, 5];
       let n = arr.length;
 
       document.write(get(arr, n));
 
 // This code is contributed by Potta Lokesh
   </script>

4

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)