算法设计（查找数组中数字的出现频率） _数据结构

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
C#
Python3
的PHP
CPP
Java
Python3
C#

给定一个数组a[]和一个元素x, 找到a[]中x出现的次数或频率。
例子：

Input: a[] = {0, 5, 5, 5, 4} x = 5 Output : 3Input: a[] = {1, 2, 3} x = 4 Output : 0

推荐：请尝试使用{IDE}首先, 在继续解决方案之前。如果数组未排序
这个想法很简单, 我们将count初始化为0。我们以线性方式遍历数组。对于与x匹配的每个元素, 我们都增加计数。最后我们返回计数。
下面是该方法的实现。
C ++

// CPP program to count occurrences of an // element in an unsorted array #include< iostream> using namespace std; int frequency( int a[], int n, int x) { int count = 0; for ( int i=0; i < n; i++) if (a[i] == x) count++; return count; }// Driver program int main() { int a[] = {0, 5, 5, 5, 4}; int x = 5; int n = sizeof (a)/ sizeof (a[0]); cout < < frequency(a, n, x); return 0; }

Java

// Java program to count // occurrences of an // element in an unsorted // arrayimport java.io.*; class GFG {static int frequency( int a[], int n, int x) { int count = 0 ; for ( int i= 0 ; i < n; i++) if (a[i] == x) count++; return count; }// Driver program public static void main (String[] args) {int a[] = { 0 , 5 , 5 , 5 , 4 }; int x = 5 ; int n = a.length; System.out.println(frequency(a, n, x)); } }// This code is contributed // by Ansu Kumari

// C# program to count // occurrences of an // element in an unsorted // array using System; class GFG {static int frequency( int []a, int n, int x) { int count = 0; for ( int i=0; i < n; i++) if (a[i] == x) count++; return count; }// Driver program static public void Main (){int []a = {0, 5, 5, 5, 4}; int x = 5; int n = a.Length; Console.Write(frequency(a, n, x)); } }// This code is contributed // by Anuj_67

Python3

# Python program to count # occurrences of an # element in an unsorted # array def frequency(a, x): count = 0for i in a: if i = = x: count + = 1 return count# Driver program a = [ 0 , 5 , 5 , 5 , 4 ] x = 5 print (frequency(a, x))# This code is contributed by Ansu Kumari

的PHP

< ?php // PHP program to count occurrences of an // element in an unsorted arrayfunction frequency( $a , $n , $x ) { $count = 0; for ( $i = 0; $i < $n ; $i ++) if ( $a [ $i ] == $x ) $count ++; return $count ; }// Driver Code $a = array (0, 5, 5, 5, 4); $x = 5; $n = sizeof( $a ); echo frequency( $a , $n , $x ); // This code is contributed by ajit ?>

输出如下：

3

时间复杂度：O(n)
辅助空间：O(1)
如果数组已排序
我们可以将方法应用于已排序和未排序。但是对于有序数组, 我们可以优化它以使用O(Log n)时间工作二元搜寻。请参阅下面的文章以了解详细信息。计算排序数组中的出现次数(或频率).
如果单个数组上有多个查询
我们可以用
杂凑
存储所有元素的频率。然后, 我们可以在O(1)时间内回答所有查询。请参考
未排序数组中每个元素的频率
有关详细信息。
CPP

// CPP program to answer queries for frequencies // in O(1) time. #include < bits/stdc++.h> using namespace std; unordered_map< int , int > hm; void countFreq( int a[], int n) { // Insert elements and their // frequencies in hash map. for ( int i=0; i< n; i++) hm[a[i]]++; }// Return frequency of x (Assumes that // countFreq() is called before) int query( int x) { return hm[x]; }// Driver program int main() { int a[] = {1, 3, 2, 4, 2, 1}; int n = sizeof (a)/ sizeof (a[0]); countFreq(a, n); cout < < query(2) < < endl; cout < < query(3) < < endl; cout < < query(5) < < endl; return 0; }

Java

// Java program to answer // queries for frequencies // in O(1) time.import java.io.*; import java.util.*; class GFG {static HashMap < Integer, Integer> hm = new HashMap< Integer, Integer> (); static void countFreq( int a[], int n) { // Insert elements and their // frequencies in hash map. for ( int i= 0 ; i< n; i++) if (hm.containsKey(a[i]) ) hm.put(a[i], hm.get(a[i]) + 1 ); else hm.put(a[i] , 1 ); }// Return frequency of x (Assumes that // countFreq() is called before) static int query( int x) { if (hm.containsKey(x)) return hm.get(x); return 0 ; }// Driver program public static void main (String[] args) { int a[] = { 1 , 3 , 2 , 4 , 2 , 1 }; int n = a.length; countFreq(a, n); System.out.println(query( 2 )); System.out.println(query( 3 )); System.out.println(query( 5 )); } }// This code is contributed by Ansu Kumari

Python3

# Python program to # answer queries for # frequencies # in O(1) time.hm = {}def countFreq(a): global hm# Insert elements and their # frequencies in hash map.for i in a: if i in hm: hm[i] + = 1 else : hm[i] = 1# Return frequency # of x (Assumes that # countFreq() is # called before) def query(x): if x in hm: return hm[x] return 0# Driver program a = [ 1 , 3 , 2 , 4 , 2 , 1 ] countFreq(a) print (query( 2 )) print (query( 3 )) print (query( 5 ))# This code is contributed # by Ansu Kumari

// C# program to answer // queries for frequencies // in O(1) time. using System; using System.Collections.Generic; class GFG {static Dictionary < int , int > hm = new Dictionary< int , int > (); static void countFreq( int []a, int n) { // Insert elements and their // frequencies in hash map. for ( int i = 0; i < n; i++) if (hm.ContainsKey(a[i]) ) hm[a[i]] = hm[a[i]] + 1; else hm.Add(a[i], 1); }// Return frequency of x (Assumes that // countFreq() is called before) static int query( int x) { if (hm.ContainsKey(x)) return hm[x]; return 0; }// Driver code public static void Main(String[] args) { int []a = {1, 3, 2, 4, 2, 1}; int n = a.Length; countFreq(a, n); Console.WriteLine(query(2)); Console.WriteLine(query(3)); Console.WriteLine(query(5)); } }// This code is contributed by 29AjayKumar

输出：