Dada una array arr[] , la tarea es encontrar la cantidad de veces que el entero actual ya se ha producido durante el recorrido de la array.
Ejemplos :
Entrada : arr[] = {2, 3, 3, 200, 175, 2, 200, 2, 175, 3}
Salida : 0 0 1 0 0 1 1 2 1 2
Explicación : antes del índice 0, se encuentra 2 0 veces. Antes del segundo índice, 3 se encuentra una vez en el índice 1. De manera similar, antes del séptimo índice, 2 aparece dos veces y así sucesivamente.Entrada : arr[] = {200, 200, 55, 200, 55, 2, 3, 2}
Salida : 0 1 0 2 1 0 0 1
Enfoque : La tarea se puede resolver haciendo un seguimiento de las frecuencias de distintos elementos hasta el elemento actual usando un HashMap . Siga los pasos a continuación para resolver el problema:
- Cree un hashmap, diga ‘ occ ‘, para almacenar las frecuencias de los distintos elementos hasta el elemento actual
- Para el elemento actual , verifique si ya existe dentro del hashmap o no .
- Si existe, almacene la frecuencia que le corresponde, de lo contrario almacene 0 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of // times current integer has already // occurred during array traversal. void getOccurrences(vector<int>& arr) { // Store the size of array int n = arr.size(); // Hashmap to keep track of // the frequencies unordered_map<int, int> occ; for (int i = 0; i < n; ++i) { // If element is already // present inside hashmap if (occ.find(arr[i]) != occ.end()) { cout << occ[arr[i]] << " "; } else { cout << 0 << " "; } // Increment the frequency occ[arr[i]]++; } } // Driver Code int main() { vector<int> arr = { 2, 3, 3, 200, 175, 2, 200, 2, 175, 3 }; getOccurrences(arr); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the number of // times current integer has already // occurred during array traversal. static void getOccurrences(int[] arr) { // Store the size of array int n = arr.length; // Hashmap to keep track of // the frequencies HashMap<Integer, Integer> occ = new HashMap<Integer, Integer>(); for (int i = 0; i < n; ++i) { // If element is already // present inside hashmap if (occ.containsKey(arr[i])) { System.out.print(occ.get(arr[i]) + " "); // Increment the frequency occ.put(arr[i], occ.get(arr[i]) + 1); } else { System.out.print(0 + " "); // Increment the frequency occ.put(arr[i], 1); } } } // Driver Code public static void main(String[] args) { int[] arr = { 2, 3, 3, 200, 175, 2, 200, 2, 175, 3 }; getOccurrences(arr); } } // This code is contributed by ukasp.
Python3
# python3 program for the above approach # Function to find the number of # times current integer has already # occurred during array traversal. def getOccurrences(arr): # Store the size of array n = len(arr) # Hashmap to keep track of # the frequencies occ = {} for i in range(0, n): # If element is already # present inside hashmap if (arr[i] in occ): print(occ[arr[i]], end=" ") else: print(0, end=" ") # Increment the frequency occ[arr[i]] = occ[arr[i]] + 1 if arr[i] in occ else 1 # Driver Code if __name__ == "__main__": arr = [2, 3, 3, 200, 175, 2, 200, 2, 175, 3] getOccurrences(arr) # This code is contributed by rakeshsahni
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the number of // times current integer has already // occurred during array traversal. static void getOccurrences(int []arr) { // Store the size of array int n = arr.Length; // Hashmap to keep track of // the frequencies Dictionary<int, int> occ = new Dictionary<int, int>();; for (int i = 0; i < n; ++i) { // If element is already // present inside hashmap if (occ.ContainsKey(arr[i])) { Console.Write(occ[arr[i]] + " "); // Increment the frequency occ[arr[i]] = occ[arr[i]] + 1; } else { Console.Write(0 + " "); // Increment the frequency occ.Add(arr[i], 1); } } } // Driver Code public static void Main() { int []arr = { 2, 3, 3, 200, 175, 2, 200, 2, 175, 3 }; getOccurrences(arr); } } // This code is contributed by Samim Hossain Mondal.
Javascript
<script> // JavaScript code for the above approach // Function to find the number of // times current integer has already // occurred during array traversal. function getOccurrences(arr) { // Store the size of array let n = arr.length; // Hashmap to keep track of // the frequencies let occ = new Map(); for (let i = 0; i < n; ++i) { // If element is already // present inside hashmap if (occ.has(arr[i])) { document.write(occ.get(arr[i]) + " "); } else { document.write(0 + " "); } // Increment the frequency if (occ.has(arr[i])) occ.set(arr[i], occ.get(arr[i]) + 1); else occ.set(arr[i], 1); } } // Driver Code let arr = [2, 3, 3, 200, 175, 2, 200, 2, 175, 3]; getOccurrences(arr); // This code is contributed by Potta Lokesh </script>
0 0 1 0 0 1 1 2 1 2
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por shuvonmajhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA