Elemento más pequeño repetido exactamente ‘k’ veces (no limitado a rango pequeño)

Dada una array de tamaño n, el objetivo es encontrar el número más pequeño que se repite exactamente ‘k’ veces donde k > 0? 
Y 
ejemplos: 

Input : a[] = {2, 1, 3, 1, 2, 2}
        k = 3
Output : 2

Input : a[] = {3, 4, 3, 2, 1, 5, 5} 
        k = 2
Output : 3
Explanation: As 3 is smaller than 5. 
So 3 should be printed.

Hemos discutido diferentes soluciones de este problema en la publicación a continuación.
Elemento más pequeño en una array que se repite exactamente ‘k’ veces

Las soluciones discutidas anteriormente están limitadas a trabajos de rango pequeño en más de un tiempo lineal. En esta publicación se analiza una solución basada en hashing que funciona en tiempo O(n) y es aplicable a cualquier rango. A continuación se muestran los pasos abstractos.

1. Cree un mapa hash que almacene elementos y sus frecuencias. 
2. Recorrer array dada. Para cada elemento atravesado, incremente su frecuencia. 
3. Recorra el mapa hash e imprima el elemento más pequeño con frecuencia k. 

Implementación:

// C++ program to find the smallest element
// with frequency exactly k.
#include <bits/stdc++.h>
using namespace std;
 
int smallestKFreq(int a[], int n, int k)
{
    unordered_map<int, int> m;
 
    // Map is used to store the count of
    // elements present in the array
    for (int i = 0; i < n; i++)
        m[a[i]]++;
 
    // Traverse the map and find minimum
    // element with frequency k.
    int res = INT_MAX;
    for (auto it = m.begin(); it != m.end(); ++it)
        if (it->second == k)
           res = min(res, it->first);
 
    return (res != INT_MAX)? res : -1;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 2, 1, 3, 1 };
    int k = 2;
    int n = sizeof(arr) / (sizeof(arr[0]));
    cout << smallestKFreq(arr, n, k);
    return 0;
}

// Java program to find the smallest element
// with frequency exactly k.
import java.util.*;
 
class GFG {
      
    public static int smallestKFreq(int a[], int n, int k)
    {
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
      
        // Map is used to store the count of
        // elements present in the array
        for (int i = 0; i < n; i ++)
             
            if (m.containsKey(a[i]))
                m.put(a[i], m.get(a[i]) + 1);
         
           else m.put(a[i], 1);
      
        // Traverse the map and find minimum
        // element with frequency k.
        int res = Integer.MAX_VALUE;
        Set<Integer> s = m.keySet();
         
        for (int temp : s)
            if (m.get(temp) == k)
               res = Math.min(res, temp);
      
        return (res != Integer.MAX_VALUE)? res : -1;
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[] = { 2, 2, 1, 3, 1 };
        int k = 2;
         
        System.out.println(smallestKFreq(arr, arr.length, k));
      
    }
  }
// This code is contributed by Arnav Kr. Mandal.

from collections import defaultdict
import sys
 
# Python program to find the smallest element
# with frequency exactly k.
def smallestKFreq(arr, n, k):
    mp = defaultdict(lambda : 0)
 
 
    # Map is used to store the count of
    # elements present in the array
    for i in range(n):
        mp[arr[i]] += 1
 
    # Traverse the map and find minimum
    # element with frequency k.
    res = sys.maxsize
    res1 = sys.maxsize
 
    for key,values in mp.items():
 
        if values == k:
            res = min(res, key)
    return res if res != res1 else -1
 
# Driver code
arr = [2, 2, 1, 3, 1]
k = 2
n = len(arr)
print(smallestKFreq(arr, n, k))
 
# This code is contributed by Shrikant13

// C# program to find the smallest element
// with frequency exactly k.
using System;
using System.Linq;
using System.Collections.Generic;
     
class GFG
{
     
    public static int smallestKFreq(int []a, int n, int k)
    {
        Dictionary<int,int> m = new Dictionary<int,int>();
     
        // Map is used to store the count of
        // elements present in the array
        for (int i = 0; i < n; i ++)
             
            if (m.ContainsKey(a[i]))
            {
                var v = m[a[i]];
                m.Remove(a[i]);
                m.Add(a[i],v + 1);
            }
        else m.Add(a[i], 1);
     
        // Traverse the map and find minimum
        // element with frequency k.
        int res = int.MaxValue;
        HashSet<int> s = new HashSet<int>(m.Keys.ToArray());
         
        foreach (int temp in s)
            if (m[temp] == k)
            res = Math.Min(res, temp);
     
        return (res != int.MaxValue)? res : -1;
    }
     
    /* Driver code */
    public static void Main(String[] args)
    {
        int []arr = { 2, 2, 1, 3, 1 };
        int k = 2;
         
        Console.WriteLine(smallestKFreq(arr, arr.Length, k));
     
    }
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript program to find the smallest element
// with frequency exactly k.
 
 
function smallestKFreq(a, n, k) {
    let m = new Map();
 
    // Map is used to store the count of
    // elements present in the array
    for (let i = 0; i < n; i++)
 
        if (m.has(a[i]))
            m.set(a[i], m.get(a[i]) + 1);
 
        else m.set(a[i], 1);
 
    // Traverse the map and find minimum
    // element with frequency k.
    let res = Number.MAX_SAFE_INTEGER;
    let s = m.keys();
 
    for (let temp of s)
        if (m.get(temp) == k)
            res = Math.min(res, temp);
 
    return (res != Number.MAX_SAFE_INTEGER) ? res : -1;
}
 
/* Driver program to test above function */
 
let arr = [2, 2, 1, 3, 1];
let k = 2;
 
document.write(smallestKFreq(arr, arr.length, k));
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

1

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

Artículo relacionado: 
Número más pequeño que se repite k veces
Este artículo es una contribución de Gitanjali Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.