测量数组中元素的频率是一项非常方便的技能，需要解决很多有竞争力的编码问题。在很多问题中，我们需要测量各种元素的频率，比如数字、字母、符号等，作为问题的一部分。
null
天真的方法
例如：
Input : arr[] = {10, 20, 20, 10, 10, 20, 5, 20}Output : 10 3 20 4 5 1Input : arr[] = {10, 20, 20}Output : 10 2 20 1
我们运行两个循环。每件物品的计数次数。为避免重复打印，请跟踪已处理的项目。
C++
// C++ program to count frequencies of array items #include <bits/stdc++.h> using namespace std; void countFreq( int arr[], int n) { // Mark all array elements as not visited vector< int > visited(n, false ); // Traverse through array elements and // count frequencies for ( int i = 0; i < n; i++) { // Skip this element if already processed if (visited[i] == true ) continue ; // Count frequency int count = 1; for ( int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true ; count++; } } cout << arr[i] << " " << count << endl; } } int main() { int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = sizeof (arr) / sizeof (arr[0]); countFreq(arr, n); return 0; } |
JAVA
// Java program to count frequencies // of array items import java.util.*; class GFG { static void countFreq( int arr[], int n) { // Mark all array elements as not visited boolean []visited = new boolean [n]; // Traverse through array elements and // count frequencies for ( int i = 0 ; i < n; i++) { // Skip this element if already processed if (visited[i] == true ) continue ; // Count frequency int count = 1 ; for ( int j = i + 1 ; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true ; count++; } } System.out.println(arr[i] + " " + count); } } // Driver Code public static void main(String[] args) { int arr[] = { 10 , 20 , 20 , 10 , 10 , 20 , 5 , 20 }; int n = arr.length; countFreq(arr, n); } } // This code is contributed by 29AjayKumar |
Python3
# Python program to count frequencies # of array items def countFreq(arr, n): # mark all array elements as not visited visited = [ False for i in range (n)] # Traverse through array elements # and count frequencies for i in range (n): # Skip this element if already processed if visited[i] = = True : continue # count frequency count = 1 for j in range (i + 1 , n): if arr[i] = = arr[j]: visited[j] = True count + = 1 print (arr[i], count) # Driver code a = [ 10 , 20 , 20 , 10 , 10 , 20 , 5 , 20 ] n = len (a) countFreq(a, n) # This code is contributed # by Mohit kumar 29 |
C#
// C# program to count frequencies // of array items using System; class GFG { static void countFreq( int []arr, int n) { // Mark all array elements as not visited Boolean []visited = new Boolean[n]; // Traverse through array elements and // count frequencies for ( int i = 0; i < n; i++) { // Skip this element if already processed if (visited[i] == true ) continue ; // Count frequency int count = 1; for ( int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true ; count++; } } Console.WriteLine(arr[i] + " " + count); } } // Driver Code public static void Main(String[] args) { int []arr = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = arr.Length; countFreq(arr, n); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to count frequencies of array items function countFreq(arr, n) { // Mark all array elements as not visited let visited = new Array(n); visited.fill( false ); // Traverse through array elements and // count frequencies for (let i = 0; i < n; i++) { // Skip this element if already processed if (visited[i] == true ) continue ; // Count frequency let count = 1; for (let j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true ; count++; } } document.write(arr[i] + " " + count + "</br>" ); } } let arr = [ 10, 20, 20, 10, 10, 20, 5, 20 ]; let n = arr.length; countFreq(arr, n); // This code is contributed by mukesh07. </script> |
输出：
10 320 45 1
优化方法：
当元件受到数值限制时测量频率 如果我们的输入数组有小的值，我们可以使用数组元素作为计数数组和递增计数的索引。在下面的示例中，元素最多为10个。
Input : arr[] = {5, 5, 6, 6, 5, 6, 1, 2, 3, 10, 10} limit = 10Output : 1 1 2 1 3 1 5 3 6 3 10 2
C++
// C++ program to count frequencies of array items // having small values. #include <bits/stdc++.h> using namespace std; void countFreq( int arr[], int n, int limit) { // Create an array to store counts. The size // of array is limit+1 and all values are // initially 0 vector< int > count(limit+1, 0); // Traverse through array elements and // count frequencies (assuming that elements // are limited by limit) for ( int i = 0; i < n; i++) count[arr[i]]++; for ( int i = 0; i <= limit; i++) if (count[i] > 0) cout << i << " " << count[i] << endl; } int main() { int arr[] = {5, 5, 6, 6, 5, 6, 1, 2, 3, 10, 10}; int n = sizeof (arr) / sizeof (arr[0]); int limit = 10; countFreq(arr, n, limit); return 0; } |
JAVA
// Java program to count frequencies of array items // having small values. class GFG { static void countFreq( int arr[], int n, int limit) { // Create an array to store counts. The size // of array is limit+1 and all values are // initially 0 int []count = new int [limit + 1 ]; // Traverse through array elements and // count frequencies (assuming that elements // are limited by limit) for ( int i = 0 ; i < n; i++) count[arr[i]]++; for ( int i = 0 ; i <= limit; i++) if (count[i] > 0 ) System.out.println(i + " " + count[i]); } // Driver Code public static void main(String[] args) { int arr[] = { 5 , 5 , 6 , 6 , 5 , 6 , 1 , 2 , 3 , 10 , 10 }; int n = arr.length; int limit = 10 ; countFreq(arr, n, limit); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to count frequencies of # array items having small values. def countFreq(arr, n, limit): # Create an array to store counts. # The size of array is limit+1 and # all values are initially 0 count = [ 0 for i in range (limit + 1 )] # Traverse through array elements and # count frequencies (assuming that # elements are limited by limit) for i in range (n): count[arr[i]] + = 1 for i in range (limit + 1 ): if (count[i] > 0 ): print (i, count[i]) # Driver Code arr = [ 5 , 5 , 6 , 6 , 5 , 6 , 1 , 2 , 3 , 10 , 10 ] n = len (arr) limit = 10 countFreq(arr, n, limit) # This code is contributed by avanitrachhadiya2155 |
C#
// C# program to count frequencies of // array items having small values. using System; class GFG { static void countFreq( int []arr, int n, int limit) { // Create an array to store counts. // The size of array is limit+1 and // all values are initially 0 int []count = new int [limit + 1]; // Traverse through array elements and // count frequencies (assuming that // elements are limited by limit) for ( int i = 0; i < n; i++) count[arr[i]]++; for ( int i = 0; i <= limit; i++) if (count[i] > 0) Console.WriteLine(i + " " + count[i]); } // Driver Code public static void Main(String[] args) { int []arr = {5, 5, 6, 6, 5, 6, 1, 2, 3, 10, 10}; int n = arr.Length; int limit = 10; countFreq(arr, n, limit); } } // This code is contributed // by Princi Singh |
Javascript
<script> // Javascript program to count frequencies // of array items having small values. function countFreq(arr, n, limit) { // Create an array to store counts. // The size of array is limit+1 and // all values are initially 0 let count = new Array(limit + 1); count.fill(0); // Traverse through array elements and // count frequencies (assuming that // elements are limited by limit) for (let i = 0; i < n; i++) count[arr[i]]++; for (let i = 0; i <= limit; i++) if (count[i] > 0) document.write(i + " " + count[i] + "</br>" ); } // Driver code let arr = [ 5, 5, 6, 6, 5, 6, 1, 2, 3, 10, 10 ]; let n = arr.length; let limit = 10; countFreq(arr, n, limit); // This code is contributed by rameshtravel07 </script> |
输出：
1 12 13 15 36 310 2
C++
// C++ program to count frequencies of array items #include <bits/stdc++.h> using namespace std; const int limit = 255; void countFreq(string str) { // Create an array to store counts. The size // of array is limit+1 and all values are // initially 0 vector< int > count(limit+1, 0); // Traverse through string characters and // count frequencies for ( int i = 0; i < str.length(); i++) count[str[i]]++; for ( int i = 0; i <= limit; i++) if (count[i] > 0) cout << ( char )i << " " << count[i] << endl; } int main() { string str = "GeeksforGeeks" ; countFreq(str); return 0; } |
JAVA
// Java program to count frequencies of array items class GFG { static int limit = 255 ; static void countFreq(String str) { // Create an array to store counts. The size // of array is limit+1 and all values are // initially 0 int []count= new int [limit + 1 ]; // Traverse through string characters and // count frequencies for ( int i = 0 ; i < str.length(); i++) count[str.charAt(i)]++; for ( int i = 0 ; i <= limit; i++) if (count[i] > 0 ) System.out.println(( char )i + " " + count[i]); } // Driver Code public static void main(String[] args) { String str = "GeeksforGeeks" ; countFreq(str); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to count frequencies of array items limit = 255 def countFreq( Str ) : # Create an array to store counts. The size # of array is limit+1 and all values are # initially 0 count = [ 0 ] * (limit + 1 ) # Traverse through string characters and # count frequencies for i in range ( len ( Str )) : count[ ord ( Str [i])] + = 1 for i in range (limit + 1 ) : if (count[i] > 0 ) : print ( chr (i), count[i]) Str = "GeeksforGeeks" countFreq( Str ) # This code is contributed by divyeshrabadiya07 |
C#
// C# program to count frequencies // of array items using System; class GFG { static int limit = 25; static void countFreq(String str) { // Create an array to store counts. // The size of array is limit+1 and // all values are initially 0 int []count = new int [limit + 1]; // Traverse through string characters // and count frequencies for ( int i = 0; i < str.Length; i++) count[str[i] - 'A' ]++; for ( int i = 0; i <= limit; i++) if (count[i] > 0) Console.WriteLine(( char )(i + 'A' ) + " " + count[i]); } // Driver Code public static void Main(String[] args) { String str = "GEEKSFORGEEKS" ; countFreq(str); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to count frequencies of array items let limit = 255; function countFreq(str) { // Create an array to store counts. The size // of array is limit+1 and all values are // initially 0 let count= new Array(limit + 1); for (let i=0;i<count.length;i++) { count[i]=0; } // Traverse through string characters and // count frequencies for (let i = 0; i < str.length; i++) count[str[i].charCodeAt(0)]++; for (let i = 0; i <= limit; i++) { if (count[i] > 0) document.write(String.fromCharCode(i) + " " + count[i]+ "<br>" ); } } // Driver Code let str = "GeeksforGeeks" ; countFreq(str); // This code is contributed by unknown2108 </script> |
输出：
G 2e 4f 1k 2o 1r 1s 2
当元件在有限范围内时测量频率 例如，考虑只包含大写字母的字符串。字符串的元素限制在从“A”到“Z”的范围内。其思想是减去最小的元素（本例中为“A”），得到元素的索引。
C++
// C++ program to count frequencies of array items #include <bits/stdc++.h> using namespace std; const int limit = 25; void countFreq(string str) { // Create an array to store counts. The size // of array is limit+1 and all values are // initially 0 vector< int > count(limit+1, 0); // Traverse through string characters and // count frequencies for ( int i = 0; i < str.length(); i++) count[str[i] - 'A' ]++; for ( int i = 0; i <= limit; i++) if (count[i] > 0) cout << ( char )(i + 'A' ) << " " << count[i] << endl; } int main() { string str = "GEEKSFORGEEKS" ; countFreq(str); return 0; } |
JAVA
// Java program to count frequencies // of array items import java.util.*; class GFG { static int limit = 25 ; static void countFreq(String str) { // Create an array to store counts. // The size of array is limit+1 and // all values are initially 0 int []count = new int [limit + 1 ]; // Traverse through string characters // and count frequencies for ( int i = 0 ; i < str.length(); i++) count[str.charAt(i) - 'A' ]++; for ( int i = 0 ; i <= limit; i++) if (count[i] > 0 ) System.out.println(( char )(i + 'A' ) + " " + count[i]); } // Driver Code public static void main(String[] args) { String str = "GEEKSFORGEEKS" ; countFreq(str); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to count frequencies of array items limit = 25 ; def countFreq( str ): # Create an array to store counts. The size # of array is limit+1 and all values are # initially 0 count = [ 0 for i in range (limit + 1 )] # Traverse through string characters and # count frequencies for i in range ( len ( str )): count[ ord ( str [i]) - ord ( 'A' )] + = 1 for i in range (limit + 1 ): if (count[i] > 0 ): print ( chr (i + ord ( 'A' )), count[i]) # Driver code if __name__ = = '__main__' : str = "GEEKSFORGEEKS" ; countFreq( str ); # This code is contributed by Pratham76 |
C#
// C# program to count frequencies // of array items using System; class GFG { static int limit = 25; static void countFreq(String str) { // Create an array to store counts. // The size of array is limit+1 and // all values are initially 0 int []count = new int [limit + 1]; // Traverse through string characters // and count frequencies for ( int i = 0; i < str.Length; i++) count[str[i] - 'A' ]++; for ( int i = 0; i <= limit; i++) if (count[i] > 0) Console.WriteLine(( char )(i + 'A' ) + " " + count[i]); } // Driver Code public static void Main(String[] args) { String str = "GEEKSFORGEEKS" ; countFreq(str); } } // This code contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program to count frequencies // of array items let limit = 25; function countFreq(str) { // Create an array to store counts. // The size of array is limit+1 and // all values are initially 0 let count = new Array(limit + 1); for (let i=0;i<limit+1;i++) { count[i]=0; } // Traverse through string characters // and count frequencies for (let i = 0; i < str.length; i++) count[str[i].charCodeAt(0) - 'A' .charCodeAt(0)]++; for (let i = 0; i <= limit; i++) if (count[i] > 0) document.write(String.fromCharCode(i + 'A' .charCodeAt(0)) + " " + count[i]+ "<br>" ); } // Driver Code let str = "GEEKSFORGEEKS" ; countFreq(str); // This code is contributed by rag2127 </script> |
输出：
E 4F 1G 2K 2O 1R 1S 2
如果没有范围和限制，测量频率 这个想法是使用哈希( C++中的无序映射 和 哈希图 在Java中）获取频率。
C++
// C++ program to count frequencies of array items #include <bits/stdc++.h> using namespace std; void countFreq( int arr[], int n) { unordered_map< int , int > mp; // Traverse through array elements and // count frequencies for ( int i = 0; i < n; i++) mp[arr[i]]++; // Traverse through map and print frequencies for ( auto x : mp) cout << x.first << " " << x.second << endl; } int main() { int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = sizeof (arr) / sizeof (arr[0]); countFreq(arr, n); return 0; } |
JAVA
// Java program to count frequencies of array items import java.util.*; class GFG { static void countFreq( int arr[], int n) { HashMap<Integer, Integer>mp = new HashMap<Integer, Integer>(); // Traverse through array elements and // count frequencies for ( int i = 0 ; i < n; i++) { if (mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1 ); } else { mp.put(arr[i], 1 ); } } // Traverse through map and print frequencies for (Map.Entry<Integer, Integer> entry : mp.entrySet()) System.out.println(entry.getKey() + " " + entry.getValue()); } // Driver Code public static void main(String[] args) { int arr[] = { 10 , 20 , 20 , 10 , 10 , 20 , 5 , 20 }; int n = arr.length; countFreq(arr, n); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to count frequencies of array items def countFreq(arr, n): mp = {} # Traverse through array elements and # count frequencies for i in range (n): if arr[i] in mp: mp[arr[i]] + = 1 else : mp[arr[i]] = 1 # Traverse through map and print frequencies for x in sorted (mp): print (x, mp[x]) # Driver Code arr = [ 10 , 20 , 20 , 10 , 10 , 20 , 5 , 20 ] n = len (arr) countFreq(arr, n) # This code is contributed by divyesh072019 |
C#
// C# program to count frequencies of array items using System; using System.Collections.Generic; class GFG { static void countFreq( int []arr, int n) { Dictionary< int , int > mp = new Dictionary< int , int >(); // Traverse through array elements and // count frequencies for ( int i = 0 ; i < n; i++) { if (mp.ContainsKey(arr[i])) { var val = mp[arr[i]]; mp.Remove(arr[i]); mp.Add(arr[i], val + 1); } else { mp.Add(arr[i], 1); } } // Traverse through map and print frequencies foreach (KeyValuePair< int , int > entry in mp) Console.WriteLine(entry.Key + " " + entry.Value); } // Driver Code public static void Main(String[] args) { int []arr = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = arr.Length; countFreq(arr, n); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to count frequencies of array items function countFreq(arr, n) { let mp = new Map(); // Traverse through array elements and // count frequencies for (let i = 0 ; i < n; i++) { if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1); } else { mp.set(arr[i], 1); } } // Traverse through map and print frequencies for (let [key, value] of mp.entries()) document.write(key + " " + value+ "<br>" ); } // Driver Code let arr=[10, 20, 20, 10, 10, 20, 5, 20]; let n = arr.length; countFreq(arr, n); // This code is contributed by ab2127 </script> |
输出：
5 110 320 4
时间复杂性： O（n） 辅助空间： O（n）
在上述高效的解决方案中，如何按元素在输入中的显示顺序打印元素？
C++
// C++ program to count frequencies of array items #include <bits/stdc++.h> using namespace std; void countFreq( int arr[], int n) { unordered_map< int , int > mp; // Traverse through array elements and // count frequencies for ( int i = 0; i < n; i++) mp[arr[i]]++; // To print elements according to first // occurrence, traverse array one more time // print frequencies of elements and mark // frequencies as -1 so that same element // is not printed multiple times. for ( int i = 0; i < n; i++) { if (mp[arr[i]] != -1) { cout << arr[i] << " " << mp[arr[i]] << endl; mp[arr[i]] = -1; } } } int main() { int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = sizeof (arr) / sizeof (arr[0]); countFreq(arr, n); return 0; } |
JAVA
// Java program to count frequencies of array items import java.util.*; class GFG { static void countFreq( int arr[], int n) { HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse through array elements and // count frequencies for ( int i = 0 ; i < n; i++) { if (mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1 ); } else { mp.put(arr[i], 1 ); } } // To print elements according to first // occurrence, traverse array one more time // print frequencies of elements and mark // frequencies as -1 so that same element // is not printed multiple times. for ( int i = 0 ; i < n; i++) { if (mp.get(arr[i]) != - 1 ) { System.out.println(arr[i] + " " + mp.get(arr[i])); mp. put(arr[i], - 1 ); } } } // Driver Code public static void main(String[] args) { int arr[] = { 10 , 20 , 20 , 10 , 10 , 20 , 5 , 20 }; int n = arr.length; countFreq(arr, n); } } // This code is contributed by Princi Singh |
Python3
# Python3 program to count frequencies of array items def countFreq(arr, n): mp = {} # Traverse through array elements and # count frequencies for i in range (n): if arr[i] not in mp: mp[arr[i]] = 1 else : mp[arr[i]] + = 1 # To print elements according to first # occurrence, traverse array one more time # print frequencies of elements and mark # frequencies as -1 so that same element # is not printed multiple times. for i in range (n): if (mp[arr[i]] ! = - 1 ): print (arr[i], mp[arr[i]]) mp[arr[i]] = - 1 # Driver code arr = [ 10 , 20 , 20 , 10 , 10 , 20 , 5 , 20 ] n = len (arr) countFreq(arr, n) # This code is contributed by rag2127 |
C#
// C# program to count frequencies of array items using System; using System.Collections.Generic; class GFG { static void countFreq( int []arr, int n) { Dictionary< int , int > mp = new Dictionary< int , int >(); // Traverse through array elements and // count frequencies for ( int i = 0 ; i < n; i++) { if (mp.ContainsKey(arr[i])) { mp[arr[i]] = mp[arr[i]] + 1; } else { mp.Add(arr[i], 1); } } // To print elements according to first // occurrence, traverse array one more time // print frequencies of elements and mark // frequencies as -1 so that same element // is not printed multiple times. for ( int i = 0; i < n; i++) { if (mp[arr[i]] != -1) { Console.WriteLine(arr[i] + " " + mp[arr[i]]); mp[arr[i]] = - 1; } } } // Driver Code public static void Main(String[] args) { int []arr = { 10, 20, 20, 10, 10, 20, 5, 20 }; int n = arr.Length; countFreq(arr, n); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to count // frequencies of array items function countFreq(arr, n) { let mp = new Map(); // Traverse through array elements and // count frequencies for (let i = 0 ; i < n; i++) { if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1); } else { mp.set(arr[i], 1); } } // To print elements according to first // occurrence, traverse array one more time // print frequencies of elements and mark // frequencies as -1 so that same element // is not printed multiple times. for (let i = 0; i < n; i++) { if (mp.get(arr[i]) != -1) { document.write(arr[i] + " " + mp.get(arr[i]) + "<br>" ); mp.set(arr[i], -1); } } } // Driver Code let arr = [ 10, 20, 20, 10, 10, 20, 5, 20 ]; let n = arr.length; countFreq(arr, n); // This code is contributed by patel2127 </script> |
输出：
10 320 45 1
时间复杂性： O（n） 辅助空间： O（n）
在Java中，我们可以使用 LinkedHashMap .因此，我们不需要额外的循环。 很多问题都是基于频率测量的，如果我们知道如何计算给定阵列中各种元素的频率，这将是一个棘手的问题。例如，尝试以下基于频率测量的问题：
本文由 阿迪蒂亚·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
