算法设计：查找数组中数字的出现频率

2021年3月17日14:22:09 发表评论 836 次浏览

本文概述

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

例子：

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

Input  : 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
// array
  
import 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#

// 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 = 0
      
     for 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 array
  
function 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#

// 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

输出：

2
1
0

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: