Primer elemento que aparece k veces en una array

Posted on by Rudeus Greyrat

Dada una array de n enteros. La tarea es encontrar el primer elemento que ocurre k número de veces. Si no aparece ningún elemento k veces la impresión -1. La distribución de elementos enteros podría estar en cualquier rango.
Ejemplos: 

Entrada : {1, 7, 4, 3, 4, 8, 7}, k = 2 
Salida : 7 
Explicación: Tanto 7 como 4 ocurren 2 veces. Pero 7 es el primero que ocurre 2 veces. 

Entrada : {4, 1, 6, 1, 6, 4}, k = 1 
Salida : -1

Enfoque ingenuo: la idea es utilizar dos bucles anidados. uno para la selección del elemento y otro para contar la cantidad de veces que el elemento seleccionado aparece en la array dada.

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

C++

// C++ implementation to find first
// element occurring k times
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the first element
// occurring k number of times
int firstElement(int arr[], int n, int k)
{
    // This loop is used for selection
    //  of elements
    for (int i = 0; i < n; i++) {
        // Count how many time selected element
        // occurs
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j])
                count++;
        }
 
        // Check, if it occurs k times or not
        if (count == k)
            return arr[i];
    }
 
    return -1;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 7, 4, 3, 4, 8, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << firstElement(arr, n, k);
    return 0;
}

Java

public class GFG {
    // Java implementation to find first
    // element occurring k times
 
    // Function to find the first element
    // occurring k number of times
    public static int firstElement(int[] arr, int n, int k)
    {
        // This loop is used for selection
        // of elements
        for (int i = 0; i < n; i++) {
            // Count how many time selected element
            // occurs
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                }
            }
 
            // Check, if it occurs k times or not
            if (count == k) {
                return arr[i];
            }
        }
 
        return -1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 7, 4, 3, 4, 8, 7 };
        int n = arr.length;
        int k = 2;
        System.out.print(firstElement(arr, n, k));
    }
}
 
// This code is contributed by Aarti_Rathi

Python3

# Python3 implementation to
# find first element
# occurring k times
 
# function to find the
# first element occurring
# k number of times
def firstElement(arr, n, k):
 
    # dictionary to count
    # occurrences of
    # each element
    for i in arr:
      count=0
      for j in arr:
        if i==j:
          count=count+1
      if count == k:
        return i
             
    # no element occurs k times
    return -1
 
# Driver Code
if __name__=="__main__":
 
    arr = [1, 7, 4, 3, 4, 8, 7];
    n = len(arr)
    k = 2
    print(firstElement(arr, n, k))
 
# This code is contributed by Arpit Jain

C#

// C# implementation to find first
// element occurring k times
using System;
 
public class GFG {
 
    // Function to find the first element
    // occurring k number of times
    public static int firstElement(int[] arr, int n, int k)
    {
        // This loop is used for selection
        // of elements
        for (int i = 0; i < n; i++) {
            // Count how many time selected element
            // occurs
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                }
            }
 
            // Check, if it occurs k times or not
            if (count == k) {
                return arr[i];
            }
        }
 
        return -1;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = { 1, 7, 4, 3, 4, 8, 7 };
        int n = arr.Length;
        int k = 2;
        Console.Write(firstElement(arr, n, k));
    }
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Producción

7

Complejidad temporal : O(n 2 ).

Enfoque eficiente: use unordered_map para el hash, ya que no se conoce el rango. Pasos:  

  1. Atraviesa la array de elementos de izquierda a derecha.
  2. Mientras atraviesa, incremente su conteo en la tabla hash.
  3. Nuevamente, recorra la array de izquierda a derecha y verifique qué elemento tiene un recuento igual a k. Imprime ese elemento y detente.
  4. Si ningún elemento tiene una cuenta igual a k, imprima -1.

A continuación se muestra una ejecución en seco del enfoque anterior: 

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

C++

// C++ implementation to find first
// element occurring k times
#include <bits/stdc++.h>
 
using namespace std;
 
// function to find the first element
// occurring k number of times
int firstElement(int arr[], int n, int k)
{
    // unordered_map to count
    // occurrences of each element
    unordered_map<int, int> count_map;
    for (int i=0; i<n; i++)
        count_map[arr[i]]++;
     
    for (int i=0; i<n; i++) 
 
        // if count of element == k ,then
        // it is the required first element
        if (count_map[arr[i]] == k)
            return arr[i];
             
    // no element occurs k times
    return -1;
}
 
// Driver program to test above
int main()
{
    int arr[] = {1, 7, 4, 3, 4, 8, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << firstElement(arr, n, k);
    return 0;
}

Java

import java.util.HashMap;
 
// Java implementation to find first
// element occurring k times
class GFG {
 
// function to find the first element
// occurring k number of times
    static int firstElement(int arr[], int n, int k) {
        // unordered_map to count
        // occurrences of each element
 
        HashMap<Integer, Integer> count_map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = 0;
            if(count_map.get(arr[i])!=null){
                a = count_map.get(arr[i]);
            }
             
            count_map.put(arr[i], a+1);
        }
        //count_map[arr[i]]++;
 
        for (int i = 0; i < n; i++) // if count of element == k ,then
        // it is the required first element
        {
            if (count_map.get(arr[i]) == k) {
                return arr[i];
            }
        }
 
        // no element occurs k times
        return -1;
    }
 
// Driver program to test above
    public static void main(String[] args) {
        int arr[] = {1, 7, 4, 3, 4, 8, 7};
        int n = arr.length;
        int k = 2;
        System.out.println(firstElement(arr, n, k));
    }
}
 
//this code contributed by Rajput-Ji

Python3

# Python3 implementation to
# find first element
# occurring k times
 
# function to find the
# first element occurring
# k number of times
def firstElement(arr, n, k):
 
    # dictionary to count
    # occurrences of
    # each element
    count_map = {};
    for i in range(0, n):
        if(arr[i] in count_map.keys()):
            count_map[arr[i]] += 1
        else:
            count_map[arr[i]] = 1
        i += 1
     
    for i in range(0, n):
         
        # if count of element == k ,
        # then it is the required
        # first element
        if (count_map[arr[i]] == k):
            return arr[i]
        i += 1
             
    # no element occurs k times
    return -1
 
# Driver Code
if __name__=="__main__":
 
    arr = [1, 7, 4, 3, 4, 8, 7];
    n = len(arr)
    k = 2
    print(firstElement(arr, n, k))
 
# This code is contributed
# by Abhishek Sharma

C#

// C# implementation to find first
// element occurring k times
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // function to find the first element
    // occurring k number of times
    static int firstElement(int []arr, int n, int k)
    {
        // unordered_map to count
        // occurrences of each element
 
        Dictionary<int, int> count_map = new Dictionary<int,int>();
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            if(count_map.ContainsKey(arr[i]))
            {
                a = count_map[arr[i]];
                count_map.Remove(arr[i]);
                count_map.Add(arr[i], a+1);
            }
            else
                count_map.Add(arr[i], 1);
        }
        //count_map[arr[i]]++;
 
        for (int i = 0; i < n; i++) // if count of element == k ,then
        // it is the required first element
        {
            if (count_map[arr[i]] == k)
            {
                return arr[i];
            }
        }
 
        // no element occurs k times
        return -1;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = {1, 7, 4, 3, 4, 8, 7};
        int n = arr.Length;
        int k = 2;
        Console.WriteLine(firstElement(arr, n, k));
    }
}
 
// This code has been contributed by 29AjayKumar

JavaScript

<script>
 
// JavaScript implementation to find first
// element occurring k times
 
// function to find the first element
// occurring k number of times
function firstElement(arr, n, k)
{
    // unordered_map to count
    // occurrences of each element
    count_map = new Map()
    for (let i=0; i<n; i++)
        count_map[arr[i]] = 0;
    for (let i=0; i<n; i++)
        count_map[arr[i]]++;
     
    for (let i=0; i<n; i++) 
 
        // if count of element == k ,then
        // it is the required first element
        if (count_map[arr[i]] == k)
            return arr[i];
             
    // no element occurs k times
    return -1;
}
 
// Driver program to test above
 
let arr = [1, 7, 4, 3, 4, 8, 7];
let n = arr.length;
let k = 2;
document.write(firstElement(arr, n, k));
 
<script>
Producción

7

Complejidad de tiempo: O(n)
Espacio auxiliar: O(n) porque estamos usando una array auxiliar de tamaño n para almacenar el conteo

Método 3: Uso de las funciones integradas de Python:

  • Cuente las frecuencias de cada elemento usando la función Contador
  • Poligonal en el diccionario de frecuencias
  • Comprueba qué elemento tiene un recuento igual a k. Imprime ese elemento y detente.
  • Si ningún elemento tiene una cuenta igual a k, imprima -1.

C++

// C++ implementation to find first
// element occurring k times
#include <bits/stdc++.h>
using namespace std;
 
// function to find the first element
// occurring k number of times
int firstElement(int arr[], int n, int k)
{
 
  // unordered_map to count
  // occurrences of each element
  map<int, int> count_map;
  for (int i = 0; i < n; i++) {
 
    count_map[arr[i]]++;
  }
  // count_map[arr[i]]++;
 
  for (int i = 0; i < n;
       i++) // if count of element == k ,then
    // it is the required first element
  {
    if (count_map.find(arr[i]) != count_map.end()) {
      if (count_map[arr[i]] == k)
        return arr[i];
    }
  }
 
  // no element occurs k times
  return -1;
}
 
// Driver code
int main()
{
  int arr[] = { 1, 7, 4, 3, 4, 8, 7 };
  int n = sizeof(arr) / sizeof(arr[0]);
  int k = 2;
  cout << (firstElement(arr, n, k));
  return 0;
}
 
// This code is contributed by Rajput-Ji

Java

// java implementation to find first
// element occurring k times
import java.util.*;
class GFG
{
 
  // function to find the first element
  // occurring k number of times
  static int firstElement(int []arr, int n, int k)
  {
 
    // unordered_map to count
    // occurrences of each element
    HashMap<Integer,Integer> count_map = new HashMap<>();
    for (int i = 0; i < n; i++)
    {
      if(count_map.containsKey(arr[i]))
      {
 
        count_map.put(arr[i], count_map.get(arr[i])+1);
      }
      else
        count_map.put(arr[i], 1);
    }
    //count_map[arr[i]]++;
 
    for (int i = 0; i < n; i++) // if count of element == k ,then
      // it is the required first element
    {
      if (count_map.containsKey(arr[i]) )
      {
        if(count_map.get(arr[i]) == k)
          return arr[i];
      }
    }
 
    // no element occurs k times
    return -1;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int []arr = {1, 7, 4, 3, 4, 8, 7};
    int n = arr.length;
    int k = 2;
    System.out.print(firstElement(arr, n, k));
  }
}
 
// This code contributed by Rajput-Ji

Python3

# importing counter from collections
from collections import Counter
 
# Python3 implementation to find
# first element occurring k times
# function to find the  first element
# occurring  k number of times
def firstElement(arr, n, k):
 
    # calculating frequencies using Counter
    count_map = Counter(arr)
 
    for i in range(0, n):
 
        # If count of element == k ,
        # then it is the required
        # first element
        if (count_map[arr[i]] == k):
            return arr[i]
        i += 1
 
    # No element occurs k times
    return -1
 
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 7, 4, 3, 4, 8, 7]
    n = len(arr)
    k = 2
    print(firstElement(arr, n, k))
 
# This code is contributed by vikkycirus

C#

// C# implementation to find first
// element occurring k times
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // function to find the first element
    // occurring k number of times
    static int firstElement(int []arr, int n, int k)
    {
        // unordered_map to count
        // occurrences of each element
 
        Dictionary<int, int> count_map = new Dictionary<int,int>();
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            if(count_map.ContainsKey(arr[i]))
            {
                a = count_map[arr[i]];
                count_map.Remove(arr[i]);
                count_map.Add(arr[i], a+1);
            }
            else
                count_map.Add(arr[i], 1);
        }
        //count_map[arr[i]]++;
 
        for (int i = 0; i < n; i++) // if count of element == k ,then
        // it is the required first element
        {
            if (count_map[arr[i]] == k)
            {
                return arr[i];
            }
        }
 
        // no element occurs k times
        return -1;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = {1, 7, 4, 3, 4, 8, 7};
        int n = arr.Length;
        int k = 2;
        Console.WriteLine(firstElement(arr, n, k));
    }
}
 
// This code is contributed by avijitmondal1998.

JavaScript

<script>
// javascript implementation to find first
// element occurring k times
 
    // function to find the first element
    // occurring k number of times
    function firstElement(arr , n , k) {
 
        // unordered_map to count
        // occurrences of each element
        var count_map = new Map();
        for (i = 0; i < n; i++) {
            if (count_map.has(arr[i])) {
 
                count_map.set(arr[i], count_map.get(arr[i]) + 1);
            } else
                count_map.set(arr[i], 1);
        }
        // count_map[arr[i]]++;
 
        for (i = 0; i < n; i++) // if count of element == k ,then
        // it is the required first element
        {
            if (count_map.has(arr[i])) {
                if (count_map.get(arr[i]) == k)
                    return arr[i];
            }
        }
 
        // no element occurs k times
        return -1;
    }
 
    // Driver code
        var arr = [ 1, 7, 4, 3, 4, 8, 7 ];
        var n = arr.length;
        var k = 2;
        document.write(firstElement(arr, n, k));
 
// This code is contributed by Rajput-Ji
</script>
Producción

7

Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(n)

Este artículo es una contribución de Ayush Jauhari . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *