Given an array of integers, replace every element by its frequency in the array.
Examples:
Input : arr[] = { 1, 2, 5, 2, 2, 5 } Output : 1 3 2 3 3 2 Input : arr[] = { 4 5 4 5 6 6 6 } Output : 2 2 2 2 3 3 3
Approach:
- Take a hash map, which will store the frequency of all the elements in the array.
- Now, traverse once again.
- Now, replace all the elements by their frequency.
- Print the modified array.
Implementation:
C++
// C++ program to replace the elements // by their frequency in the array. #include "iostream" #include "unordered_map" using namespace std; void ReplaceElementsByFrequency( int arr[], int n) { // Hash map which will store the // frequency of the elements of the array. unordered_map< int , int > mp; for ( int i = 0; i < n; ++i) { // Increment the frequency // of the element by 1. mp[arr[i]]++; } // Replace every element by its frequency for ( int i = 0; i < n; ++i) { arr[i] = mp[arr[i]]; } } int main() { int arr[] = { 1, 2, 5, 2, 2, 5 }; int n = sizeof (arr) / sizeof (arr[0]); ReplaceElementsByFrequency(arr, n); // Print the modified array. for ( int i = 0; i < n; ++i) { cout << arr[i] << " " ; } return 0; } |
Java
import java.util.HashMap; // Java program to replace the elements // by their frequency in the array. class GFG { static void ReplaceElementsByFrequency( int arr[], int n) { // Hash map which will store the // frequency of the elements of the array. HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); for ( int i = 0 ; i < n; ++i) { // Increment the frequency // of the element by 1. if (mp.get(arr[i]) == null ) { mp.put(arr[i], 1 ); } else { mp.put(arr[i], (mp.get(arr[i]) + 1 )); } //mp[arr[i]]++; } // Replace every element by its frequency for ( int i = 0 ; i < n; ++i) { if (mp.get(arr[i]) != null ) { arr[i] = mp.get(arr[i]); } //arr[i] = mp[arr[i]]; } } public static void main(String[] args) { int arr[] = { 1 , 2 , 5 , 2 , 2 , 5 }; int n = arr.length; ReplaceElementsByFrequency(arr, n); // Print the modified array. for ( int i = 0 ; i < n; ++i) { System.out.print(arr[i] + " " ); } } } // This code contributed by 29AJayKumar |
Python3
# Python 3 program to replace the elements # by their frequency in the array. def ReplaceElementsByFrequency(arr, n): # Hash map which will store the # frequency of the elements of the array. mp = {i: 0 for i in range ( len (arr))} for i in range (n): # Increment the frequency of the # element by 1. mp[arr[i]] + = 1 # Replace every element by its frequency for i in range (n): arr[i] = mp[arr[i]] # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 5 , 2 , 2 , 5 ] n = len (arr) ReplaceElementsByFrequency(arr, n); # Print the modified array. for i in range (n): print (arr[i], end = " " ) # This code is contributed by # Sahil_shelangia |
C#
// C# program to replace the elements // by their frequency in the array. using System; using System.Collections.Generic; class GFG { static void ReplaceElementsByFrequency( int []arr, int n) { // Hash map which will store the // frequency of the elements of the array. Dictionary< int , int > mp = new Dictionary< int , int >(); for ( int i = 0; i < n; ++i) { // Increment the frequency // of the element by 1. if (!mp.ContainsKey(arr[i])) { mp.Add(arr[i], 1); } else { var a = mp[arr[i]] + 1; mp.Remove(arr[i]); mp.Add(arr[i], a); } } // Replace every element by its frequency for ( int i = 0; i < n; ++i) { if (mp[arr[i]] != 0) { arr[i] = mp[arr[i]]; } //arr[i] = mp[arr[i]]; } } // Driver code public static void Main(String[] args) { int []arr = {1, 2, 5, 2, 2, 5}; int n = arr.Length; ReplaceElementsByFrequency(arr, n); // Print the modified array. for ( int i = 0; i < n; ++i) { Console.Write(arr[i] + " " ); } } } // This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to replace the elements // by their frequency in the array. function ReplaceElementsByFrequency(arr, n) { // Hash map which will store the // frequency of the elements of the array. let mp = new Map(); for (let i = 0; i < n; ++i) { // Increment the frequency // of the element by 1. if (mp.get(arr[i]) == null ) { mp.set(arr[i], 1); } else { mp.set(arr[i], (mp.get(arr[i]) + 1)); } //mp[arr[i]]++; } // Replace every element by its frequency for (let i = 0; i < n; ++i) { if (mp.get(arr[i]) != null ) { arr[i] = mp.get(arr[i]); } //arr[i] = mp[arr[i]]; } } // Driver Code let arr = [ 1, 2, 5, 2, 2, 5 ]; let n = arr.length; ReplaceElementsByFrequency(arr, n); // Print the modified array. for (let i = 0; i < n; ++i) { document.write(arr[i] + " " ); } // This code is contributed by code_hunt </script> |
1 3 2 3 3 2
Time Complexity: O(N)
Auxiliary Space: O(N) because extra space is being used for unordered_map mp
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!