在不到O（n）的时间内找到有限范围数组中每个元素的频率-yiteyi-C++库

给定一个正整数排序数组，数组中每个元素的出现次数。假设数组中的所有元素都小于某个常数M。在不遍历整个数组的情况下执行此操作。i、 e.预期时间复杂度小于O（n）。

null

例如：

Input: arr[] = [1, 1, 1, 2, 3, 3, 5,               5, 8, 8, 8, 9, 9, 10] Output:Element 1 occurs 3 timesElement 2 occurs 1 timesElement 3 occurs 2 timesElement 5 occurs 2 timesElement 8 occurs 3 timesElement 9 occurs 2 timesElement 10 occurs 1 timesInput: arr[] = [2, 2, 6, 6, 7, 7, 7, 11] Output:Element 2 occurs 2 timesElement 6 occurs 2 timesElement 7 occurs 3 timesElement 11 occurs 1 times

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法1： 该方法采用线性搜索技术，不使用辅助空间。

方法： 如果当前元素和前一个元素相同，则遍历输入数组并增加元素的频率，否则重置频率并打印元素及其频率。
算法：
- 将频率初始化为1，并将索引设置为1。
- 从索引位置遍历数组，检查当前元素是否等于上一个元素。
- 如果是，增加频率和索引，并重复步骤2。否则，打印元素及其频率，然后重复步骤2。
- 最后（角盒），打印最后一个元素及其频率。
实施：

C++

                         // C++ program to count number of occurrences of                       
                         // each element in the array in O(n) time and O(1) space                       
           
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
                         void                                     findFrequencies(                                     int                                     ele[],                                     int                                     n)                       
                         {                       
                                                 int                                     freq = 1;                       
                                                 int                                     idx = 1;                       
                                                 int                                     element = ele[0];                       
                                                 while                                     (idx < n) {                       
                                                 // check if the current element is equal to                       
                                                 // previous element.                       
                                                 if                                     (ele[idx - 1] == ele[idx]) {                       
                                                 freq++;                       
                                                 idx++;                       
                                                 }                       
                                                 else                                     {                       
                                                 cout << element <<                                     " "                                     << freq << endl;                       
                                                 element = ele[idx];                       
                                                 idx++;                       
                                   
                                                 // reset the frequency                       
                                                 freq = 1;                       
                                                 }                       
                                                 }                       
                                   
                                                 // print the last element and its frequency                       
                                                 cout << element <<                                     " "                                     << freq;                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 cout <<                                     "---frequencies in a sorted array----"                                     << endl;                       
                                                 int                                     arr[]                       
                                                 = { 10, 20, 30, 30, 30, 40, 50, 50, 50, 50, 70 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 findFrequencies(arr, n);                       
                         }                       
           
                         // This code is contributed by anushkaseehh                       

JAVA

                         // Java program to count number of occurrences of                       
                         // each element in the array in O(n) time and O(1) space                       
           
           
                                                 function                                     void                                     findFrequencies(ele)                       
                                                 {                       
                                                 var freq =                                     1                                     ;                       
                                                 var idx =                                     1                                     ;                       
                                                 var element = ele[                                     0                                     ];                       
                                                 while                                     (idx < ele.length) {                       
                                                 // check if the current element is equal to                       
                                                 // previous element.                       
                                                 if                                     (ele[idx -                                     1                                     ] == ele[idx]) {                       
                                                 freq++;                       
                                                 idx++;                       
                                                 }                       
                                                 else                                     {                       
                                                 document.write(element +                                     " "                                     + freq+                                     "<br>"                                     );                       
                                                 element = ele[idx];                       
                                                 idx++;                       
                                                 // reset the frequency                       
                                                 freq =                                     1                                     ;                       
                                                 }                       
                                                 }                       
                                                 // print the last element and its frequency                       
                                                 document.write(element +                                     " "                                     + freq +                                     "<br>"                                     );                       
                                                 }                       
                                                 // Driver code                       
                                   
                                                 document.write(                       
                                                 "---frequencies in a sorted array----"                                     +                                     "<br>"                                     );                       
                                                 findFrequencies(                                     new                                     Array (                                     10                                     ,                                     20                                     ,                                     30                                     ,                                     30                                     ,                                     30                                     ,                                     40                                     ,                       
                                                 50                                     ,                                     50                                     ,                                     50                                     ,                                     50                                     ,                                     70                                     ));                       
                                   
                         //this code is contributed by shivanisinghss2110                       

Python3

                         # python program to count number of occurrences of                       
                         # each element in the array in O(n) time and O(1) space                       
                         def                                     findFrequencies(ele, n):                       
           
                                                 freq                                     =                                     1                       
                                                 idx                                     =                                     1                       
                                                 element                                     =                                     ele[                                     0                                     ]                       
                                                 while                                     (idx < n):                       
                                   
                                                 # check if the current element is equal to                       
                                                 # previous element.                       
                                                 if                                     (ele[idx                                     -                                     1                                     ]                                     =                                     =                                     ele[idx]):                       
                                                 freq                                     +                                     =                                     1                       
                                                 idx                                     +                                     =                                     1                       
                                   
                                                 else                                     :                       
                                                 print                                     (element ,                                     " "                                     ,freq);                       
                                                 element                                     =                                     ele[idx]                       
                                                 idx                                     +                                     =                                     1                       
                                   
                                                 # reset the frequency                       
                                                 freq                                     =                                     1                       
                                   
                                                 # print the last element and its frequency                       
                                                 print                                     (element ,                                     " "                                     , freq);                       
           
                         print                                     (                                     "---frequencies in a sorted array----"                                     );                       
                         arr                                     =                                     [                                     10                                     ,                                     20                                     ,                                     30                                     ,                                     30                                     ,                                     30                                     ,                                     40                                     ,                                     50                                     ,                                     50                                     ,                                     50                                     ,                                     50                                     ,                                     70                                     ];                       
                         n                                     =                                     len                                     (arr)                       
                         findFrequencies(arr, n)                       
           
                         # This code is contributed by shivanisinghss2110                       

C#

                         // C# program to count number of occurrences of                       
                         // each element in the array in O(n) time and O(1) space                       
                         using                                     System;                       
                         class                                     GFG {                       
           
                                                 public                                     static                                     void                                     findFrequencies(                                     int                                     [] ele)                       
                                                 {                       
                                                 int                                     freq = 1;                       
                                                 int                                     idx = 1;                       
                                                 int                                     element = ele[0];                       
                                                 while                                     (idx < ele.Length)                       
                                                 {                       
                                   
                                                 // check if the current element is equal to                       
                                                 // previous element.                       
                                                 if                                     (ele[idx - 1] == ele[idx]) {                       
                                                 freq++;                       
                                                 idx++;                       
                                                 }                       
                                                 else                                     {                       
                                                 Console.WriteLine(element +                                     " "                                     + freq);                       
                                                 element = ele[idx];                       
                                                 idx++;                       
                                   
                                                 // reset the frequency                       
                                                 freq = 1;                       
                                                 }                       
                                                 }                       
                                   
                                                 // print the last element and its frequency                       
                                                 Console.WriteLine(element +                                     " "                                     + freq);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 Console.WriteLine(                       
                                                 "---frequencies in a sorted array----"                                     );                       
                                                 findFrequencies(                                     new                                     int                                     [] { 10, 20, 30, 30, 30, 40,                       
                                                 50, 50, 50, 50, 70 });                       
                                                 }                       
                         }                       

Javascript

                         <script>                       
                         // JavaScript program to count number of occurrences of                       
                         // each element in the array in O(n) time and O(1) space                       
                                                 function                                     void findFrequencies(ele)                       
                                                 {                       
                                                 var                                     freq = 1;                       
                                                 var                                     idx = 1;                       
                                                 var                                     element = ele[0];                       
                                                 while                                     (idx < ele.length)                       
                                                 {                       
                                   
                                                 // check if the current element is equal to                       
                                                 // previous element.                       
                                                 if                                     (ele[idx - 1] == ele[idx]) {                       
                                                 freq++;                       
                                                 idx++;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 document.write(element +                                     " "                                     + freq);                       
                                                 element = ele[idx];                       
                                                 idx++;                       
                                   
                                                 // reset the frequency                       
                                                 freq = 1;                       
                                                 }                       
                                                 }                       
                                   
                                                 // print the last element and its frequency                       
                                                 document.write(element +                                     " "                                     + freq);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 document.write(                       
                                                 "---frequencies in a sorted array----"                                     );                       
                                                 findFrequencies(                                     new                                     var                                     [] { 10, 20, 30, 30, 30, 40,                       
                                                 50, 50, 50, 50, 70 });                       
                                   
                         // This code is contributed by shivanisinghss2110                       
                         </script>                       

输出

---frequencies in a sorted array----10 120 130 340 150 470 1

方法2 : 这种方法使用了线性搜索解决以下问题。

方法： 其思想是遍历输入数组，对于数组中的每个不同元素，将其频率存储在哈希图，最后打印HashMap。
算法：
1. 创建一个HashMap将频率映射到元素，即存储元素频率对。
2. 从头到尾遍历阵列。
3. 对于阵列中的每个元素，更新频率，即 hm[array[i]]++
4. 遍历HashMap并打印元素频率对。
实施：

C++

                         // C++ program to count number of occurrences of                       
                         // each element in the array #include <iostream>                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // It prints number of                       
                         // occurrences of each element in the array.                       
                         void                                     findFrequency(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // HashMap to store frequencies                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > mp;                       
           
                                                 // traverse the array                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 // update the frequency                       
                                                 mp[arr[i]]++;                       
                                                 }                       
           
                                                 // traverse the hashmap                       
                                                 for                                     (                                     auto                                     i : mp) {                       
                                                 cout <<                                     "Element "                                     << i.first <<                                     " occurs "                       
                                                 << i.second <<                                     " times"                                     << endl;                       
                                                 }                       
                         }                       
           
                         // Driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 1, 1, 2, 3, 3, 5, 5,                       
                                                 8, 8, 8, 9, 9, 10 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 findFrequency(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number                       
                         // of occurrences of each                       
                         // element in the array                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
                         class                                     GFG                       
                         {                       
           
                                                 // It prints number of                       
                                                 // occurrences of each                       
                                                 // element in the array.                       
                                                 static                                     void                                     findFrequency(                                     int                                     [] arr,                       
                                                 int                                     n)                       
                                                 {                       
                                                 Map<Integer, Integer> mp                       
                                                 =                                     new                                     HashMap<Integer, Integer>();                       
           
                                                 // traverse the array                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
           
                                                 // update the frequency                       
                                                 if                                     (!mp.containsKey(arr[i]))                       
                                                 mp.put(arr[i],                                     0                                     );                       
           
                                                 mp.put(arr[i],mp.get(arr[i])+                                     1                                     );                       
                                                 }                       
           
                                                 // traverse the hashmap                       
                                                 for                                     (Map.Entry<Integer, Integer> kvp : mp.entrySet())                       
                                                 {                       
                                                 System.out.println(                                     "Element "                                     + kvp.getKey() +                       
                                                 " occurs "                                     + kvp.getValue() +                       
                                                 " times"                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // Driver function                       
                                                 public                                     static                                     void                                     main (String[] args) {                       
           
           
                                                 int                                     [] arr = {                                     1                                     ,                                     1                                     ,                                     1                                     ,                                     2                                     ,                       
                                                 3                                     ,                                     3                                     ,                                     5                                     ,                                     5                                     ,                       
                                                 8                                     ,                                     8                                     ,                                     8                                     ,                                     9                                     ,                       
                                                 9                                     ,                                     10                                     };                       
                                                 int                                     n = arr.length;                       
                                                 findFrequency(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by avanitrachhadiya2155                       

Python3

                         # Python program to count number of occurrences of                       
                         # each element in the array #include <iostream>                       
           
                         # It prints number of                       
                         # occurrences of each element in the array.                       
                         def                                     findFrequency(arr, n):                       
                                   
                                                 # HashMap to store frequencies                       
                                                 mp                                     =                                     {}                       
           
                                                 # traverse the array                       
                                                 for                                     i                                     in                                     range                                     (n):                       
           
                                                 # update the frequency                       
                                                 if                                     arr[i]                                     not                                     in                                     mp:                       
                                                 mp[arr[i]]                                     =                                     0                       
                                                 mp[arr[i]]                                     +                                     =                                     1                       
                                   
                                                 # traverse the hashmap                       
                                                 for                                     i                                     in                                     mp:                       
                                                 print                                     (                                     "Element"                                     , i,                                     "occurs"                                     , mp[i],                                     "times"                                     )                       
                                   
                         # Driver function                       
                         arr                                     =                                     [                                     1                                     ,                                     1                                     ,                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     3                                     ,                                     5                                     ,                                     5                                     ,                                     8                                     ,                                     8                                     ,                                     8                                     ,                                     9                                     ,                                     9                                     ,                                     10                                     ]                       
                         n                                     =                                     len                                     (arr)                       
           
                         findFrequency(arr, n)                       
                                   
                         # This code is contributed by shubhamsingh10                       

C#

                         // C# program to count number                       
                         // of occurrences of each                       
                         // element in the array                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                         class                                     GFG{                       
           
                         // It prints number of                       
                         // occurrences of each                       
                         // element in the array.                       
                         static                                     void                                     findFrequency(                                     int                                     [] arr,                       
                                                 int                                     n)                       
                         {                       
                                                 // HashMap to store frequencies                       
                                                 Dictionary <                                     int                                     ,                       
                                                 int                                     > mp =                       
                                                 new                                     Dictionary<                                     int                                     ,                       
                                                 int                                     >();                       
           
                                                 // traverse the array                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // update the frequency                       
                                                 if                                     (!mp.ContainsKey(arr[i]))                       
                                                 mp[arr[i]] = 0;                       
           
                                                 mp[arr[i]]++;                       
                                                 }                       
           
                                                 // traverse the hashmap                       
                                                 foreach                                     (KeyValuePair<                                     int                                     ,                       
                                                 int                                     > kvp                                     in                                     mp)                       
                                                 Console.WriteLine(                                     "Element "                                     + kvp.Key +                       
                                                 " occurs "                                     + kvp.Value +                       
                                                 " times"                                     );                       
                         }                       
           
                         // Driver function                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     [] arr = {1, 1, 1, 2,                       
                                                 3, 3, 5, 5,                       
                                                 8, 8, 8, 9,                       
                                                 9, 10};                       
                                                 int                                     n = arr.Length;                       
                                                 findFrequency(arr, n);                       
                         }                       
                         }                       
           
                         // This code is contributed by Chitranayal                       

Javascript

                         <script>                       
           
                         // Javascript program to count number                       
                         // of occurrences of each                       
                         // element in the array                       
           
                         // It prints number of                       
                         // occurrences of each                       
                         // element in the array.                       
                         function                                     findFrequency(arr, n)                       
                         {                       
                                                 let mp =                                     new                                     Map();                       
                                   
                                                 // Traverse the array                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // Update the frequency                       
                                                 if                                     (!mp.has(arr[i]))                       
                                                 mp.set(arr[i],0);                       
                                   
                                                 mp.set(arr[i], mp.get(arr[i]) + 1);                       
                                                 }                       
                                   
                                                 // Traverse the hashmap                       
                                                 for                                     (let [key, value] of mp.entries())                       
                                                 {                       
                                                 document.write(                                     "Element "                                     + key +                       
                                                 " occurs "                                     + value +                       
                                                 " times<br>"                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         let arr = [ 1, 1, 1, 2, 3, 3, 5,                       
                                                 5, 8, 8, 8, 9, 9, 10 ];                       
                         let n = arr.length;                       
           
                         findFrequency(arr, n);                       
           
                         // This code is contributed by patel2127                       
           
                         </script>                       

输出

Element 10 occurs 1 timesElement 2 occurs 1 timesElement 9 occurs 2 timesElement 1 occurs 3 timesElement 8 occurs 3 timesElement 3 occurs 2 timesElement 5 occurs 2 times

复杂性分析：

时间复杂性： O（n），只需要遍历数组一次。
空间复杂性： O（n），要在HashMap中存储元素，需要额外的空间。

方法3 : 该方法使用二进制搜索技术来获得解。

方法： 如果对其所有元素进行排序，则问题可以在不到O（n）的时间内解决，即，如果阵列中存在相似的元素，则元素位于相邻的子阵列中，或者可以说，如果子阵列的末端相同，则子阵列中的所有元素都相等。因此，该元素的计数是子数组的大小，该子数组的所有元素都不需要计数。
算法：
1. 创建一个HashMap( 陛下 )存储元素的频率。
2. 创建一个接受数组和大小的递归函数。
3. 检查数组的第一个元素是否等于最后一个元素。如果相等，则所有元素都相同，并通过 hm[数组[0]+=大小
4. 否则，将数组分成两个相等的部分，并对这两部分递归调用函数。
5. 遍历hashmap并打印元素频率对。
实施：

C++

                         // C++ program to count number of occurrences of                       
                         // each element in the array in less than O(n) time                       
                         #include <iostream>                       
                         #include <vector>                       
                         using                                     namespace                                     std;                       
           
                         // A recursive function to count number of occurrences                       
                         // for each element in the array without traversing                       
                         // the whole array                       
                         void                                     findFrequencyUtil(                                     int                                     arr[],                                     int                                     low,                                     int                                     high,                       
                                                 vector<                                     int                                     >& freq)                       
                         {                       
                                                 // If element at index low is equal to element                       
                                                 // at index high in the array                       
                                                 if                                     (arr[low] == arr[high]) {                       
                                                 // increment the frequency of the element                       
                                                 // by count of elements between high and low                       
                                                 freq[arr[low]] += high - low + 1;                       
                                                 }                       
                                                 else                                     {                       
                                                 // Find mid and recurse for left and right                       
                                                 // subarray                       
                                                 int                                     mid = (low + high) / 2;                       
                                                 findFrequencyUtil(arr, low, mid, freq);                       
                                                 findFrequencyUtil(arr, mid + 1, high, freq);                       
                                                 }                       
                         }                       
           
                         // A wrapper over recursive function                       
                         // findFrequencyUtil(). It print number of                       
                         // occurrences of each element in the array.                       
                         void                                     findFrequency(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // create a empty vector to store frequencies                       
                                                 // and initialize it by 0. Size of vector is                       
                                                 // maximum value (which is last value in sorted                       
                                                 // array) plus 1.                       
                                                 vector<                                     int                                     > freq(arr[n - 1] + 1, 0);                       
           
                                                 // Fill the vector with frequency                       
                                                 findFrequencyUtil(arr, 0, n - 1, freq);                       
           
                                                 // Print the frequencies                       
                                                 for                                     (                                     int                                     i = 0; i <= arr[n - 1]; i++)                       
                                                 if                                     (freq[i] != 0)                       
                                                 cout <<                                     "Element "                                     << i <<                                     " occurs "                       
                                                 << freq[i] <<                                     " times"                                     << endl;                       
                         }                       
           
                         // Driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 1, 1, 2, 3, 3, 5, 5,                       
                                                 8, 8, 8, 9, 9, 10 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 findFrequency(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number of occurrences of                       
                         // each element in the array in less than O(n) time                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                                                 // A recursive function to count number of occurrences                       
                                                 // for each element in the array without traversing                       
                                                 // the whole array                       
                                                 static                                     void                                     findFrequencyUtil(                                     int                                     arr[],                                     int                                     low,                       
                                                 int                                     high,                                     int                                     [] freq)                       
                                                 {                       
                                                 // If element at index low is equal to element                       
                                                 // at index high in the array                       
                                                 if                                     (arr[low] == arr[high]) {                       
                                                 // increment the frequency of the element                       
                                                 // by count of elements between high and low                       
                                                 freq[arr[low]] += high - low +                                     1                                     ;                       
                                                 }                       
                                                 else                                     {                       
                                                 // Find mid and recurse for left and right                       
                                                 // subarray                       
                                                 int                                     mid = (low + high) /                                     2                                     ;                       
                                                 findFrequencyUtil(arr, low, mid, freq);                       
                                                 findFrequencyUtil(arr, mid +                                     1                                     , high, freq);                       
                                                 }                       
                                                 }                       
           
                                                 // A wrapper over recursive function                       
                                                 // findFrequencyUtil(). It print number of                       
                                                 // occurrences of each element in the array.                       
                                                 static                                     void                                     findFrequency(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 // create a empty vector to store frequencies                       
                                                 // and initialize it by 0. Size of vector is                       
                                                 // maximum value (which is last value in sorted                       
                                                 // array) plus 1.                       
                                                 int                                     [] freq =                                     new                                     int                                     [arr[n -                                     1                                     ] +                                     1                                     ];                       
           
                                                 // Fill the vector with frequency                       
                                                 findFrequencyUtil(arr,                                     0                                     , n -                                     1                                     , freq);                       
           
                                                 // Print the frequencies                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <= arr[n -                                     1                                     ]; i++)                       
                                                 if                                     (freq[i] !=                                     0                                     )                       
                                                 System.out.println(                                     "Element "                                     + i +                                     " occurs "                                     + freq[i] +                                     " times"                                     );                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     1                                     ,                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     3                                     ,                                     5                                     ,                       
                                                 5                                     ,                                     8                                     ,                                     8                                     ,                                     8                                     ,                                     9                                     ,                                     9                                     ,                                     10                                     };                       
                                                 int                                     n = arr.length;                       
           
                                                 findFrequency(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Python3

                         # Python 3 program to count number of occurrences of                       
                         # each element in the array in less than O(n) time                       
           
                         # A recursive function to count number of occurrences                       
                         # for each element in the array without traversing                       
                         # the whole array                       
                         def                                     findFrequencyUtil(arr, low, high, freq):                       
                                   
                                                 # If element at index low is equal to element                       
                                                 # at index high in the array                       
                                                 if                                     (arr[low]                                     =                                     =                                     arr[high]):                       
                                   
                                                 # increment the frequency of the element                       
                                                 # by count of elements between high and low                       
                                                 freq[arr[low]]                                     +                                     =                                     high                                     -                                     low                                     +                                     1                       
                                   
                                                 else                                     :                       
                                   
                                                 # Find mid and recurse for left                       
                                                 # and right subarray                       
                                                 mid                                     =                                     int                                     ((low                                     +                                     high)                                     /                                     2                                     )                       
                                                 findFrequencyUtil(arr, low, mid, freq)                       
                                                 findFrequencyUtil(arr, mid                                     +                                     1                                     , high, freq)                       
                                   
                         # A wrapper over recursive function                       
                         # findFrequencyUtil(). It print number of                       
                         # occurrences of each element in the array.                       
                         def                                     findFrequency(arr, n):                       
                                   
                                                 # create a empty vector to store frequencies                       
                                                 # and initialize it by 0. Size of vector is                       
                                                 # maximum value (which is last value in sorted                       
                                                 # array) plus 1.                       
                                                 freq                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (n                                     -                                     1                                     +                                     1                                     )]                       
                                   
                                                 # Fill the vector with frequency                       
                                                 findFrequencyUtil(arr,                                     0                                     , n                                     -                                     1                                     , freq)                       
           
                                                 # Print the frequencies                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , arr[n                                     -                                     1                                     ]                                     +                                     1                                     ,                                     1                                     ):                       
                                                 if                                     (freq[i] !                                     =                                     0                                     ):                       
                                                 print                                     (                                     "Element"                                     , i,                                     "occurs"                                     ,                       
                                                 freq[i],                                     "times"                                     )                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 arr                                     =                                     [                                     1                                     ,                                     1                                     ,                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     3                                     ,                                     5                                     ,                       
                                                 5                                     ,                                     8                                     ,                                     8                                     ,                                     8                                     ,                                     9                                     ,                                     9                                     ,                                     10                                     ]                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 findFrequency(arr, n)                       
                                   
                         # This code is contributed by                       
                         # Surendra_Gangwar                       

C#

                         // C# program to count number of occurrences of                       
                         // each element in the array in less than O(n) time                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // A recursive function to count number of occurrences                       
                                                 // for each element in the array without traversing                       
                                                 // the whole array                       
                                                 static                                     void                                     findFrequencyUtil(                                     int                                     [] arr,                                     int                                     low,                       
                                                 int                                     high,                                     int                                     [] freq)                       
                                                 {                       
                                                 // If element at index low is equal to element                       
                                                 // at index high in the array                       
                                                 if                                     (arr[low] == arr[high]) {                       
                                                 // increment the frequency of the element                       
                                                 // by count of elements between high and low                       
                                                 freq[arr[low]] += high - low + 1;                       
                                                 }                       
                                                 else                                     {                       
                                                 // Find mid and recurse for left and right                       
                                                 // subarray                       
                                                 int                                     mid = (low + high) / 2;                       
                                                 findFrequencyUtil(arr, low, mid, freq);                       
                                                 findFrequencyUtil(arr, mid + 1, high, freq);                       
                                                 }                       
                                                 }                       
           
                                                 // A wrapper over recursive function                       
                                                 // findFrequencyUtil(). It print number of                       
                                                 // occurrences of each element in the array.                       
                                                 static                                     void                                     findFrequency(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 // create a empty vector to store frequencies                       
                                                 // and initialize it by 0. Size of vector is                       
                                                 // maximum value (which is last value in sorted                       
                                                 // array) plus 1.                       
                                                 int                                     [] freq =                                     new                                     int                                     [arr[n - 1] + 1];                       
           
                                                 // Fill the vector with frequency                       
                                                 findFrequencyUtil(arr, 0, n - 1, freq);                       
           
                                                 // Print the frequencies                       
                                                 for                                     (                                     int                                     i = 0; i <= arr[n - 1]; i++)                       
                                                 if                                     (freq[i] != 0)                       
                                                 Console.WriteLine(                                     "Element "                                     + i +                                     " occurs "                                     + freq[i] +                                     " times"                                     );                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     [] arr = { 1, 1, 1, 2, 3, 3, 5,                       
                                                 5, 8, 8, 8, 9, 9, 10 };                       
                                                 int                                     n = arr.Length;                       
           
                                                 findFrequency(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Princi Singh                       

Javascript

                         <script>                       
                         // Javascript program to count number of occurrences of                       
                         // each element in the array in less than O(n) time                       
                                   
                                                 // A recursive function to count number of occurrences                       
                                                 // for each element in the array without traversing                       
                                                 // the whole array                       
                                                 function                                     findFrequencyUtil(arr, low, high, freq)                       
                                                 {                       
                                   
                                                 // If element at index low is equal to element                       
                                                 // at index high in the array                       
                                                 if                                     (arr[low] == arr[high])                       
                                                 {                       
                                   
                                                 // increment the frequency of the element                       
                                                 // by count of elements between high and low                       
                                                 freq[arr[low]] += high - low + 1;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                   
                                                 // Find mid and recurse for left and right                       
                                                 // subarray                       
                                                 let mid = Math.floor((low + high) / 2);                       
                                                 findFrequencyUtil(arr, low, mid, freq);                       
                                                 findFrequencyUtil(arr, mid + 1, high, freq);                       
                                                 }                       
                                                 }                       
                                   
                                                 // A wrapper over recursive function                       
                                                 // findFrequencyUtil(). It print number of                       
                                                 // occurrences of each element in the array.                       
                                                 function                                     findFrequency(arr, n)                       
                                                 {                       
                                   
                                                 // create a empty vector to store frequencies                       
                                                 // and initialize it by 0. Size of vector is                       
                                                 // maximum value (which is last value in sorted                       
                                                 // array) plus 1.                       
                                                 let freq =                                     new                                     Array(arr[n - 1] + 1);                       
                                   
                                                 for                                     (let i = 0; i < arr[n - 1] + 1; i++)                       
                                                 {                       
                                                 freq[i] = 0;                       
                                                 }                       
                                   
                                                 // Fill the vector with frequency                       
                                                 findFrequencyUtil(arr, 0, n - 1, freq);                       
                                   
                                                 // Print the frequencies                       
                                                 for                                     (let i = 0; i <= arr[n - 1]; i++)                       
                                                 if                                     (freq[i] != 0)                       
                                                 document.write(                                     "Element "                                     + i +                                     " occurs "                                     + freq[i] +                                     " times<br>"                                     );                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 let arr = [1, 1, 1, 2, 3, 3, 5,                       
                                                 5, 8, 8, 8, 9, 9, 10 ];                       
                                                 let n = arr.length;                       
                                                 findFrequency(arr, n);                       
                                   
                                                 // This code is contributed by rag2127.                       
                         </script>                       

输出

Element 1 occurs 3 timesElement 2 occurs 1 timesElement 3 occurs 2 timesElement 5 occurs 2 timesElement 8 occurs 3 timesElement 9 occurs 2 timesElement 10 occurs 1 times

复杂性分析：

时间复杂性： O（m logn）。其中m是大小为n的数组中不同元素的数量。由于m<=m（一个常数）（元素在有限范围内），该解的时间复杂度为O（logn）。
空间复杂性： O（n）。要在HashMap中存储元素，需要额外的空间。

方法4

在这种方法中，我们通过修改哈希映射的内容来使用与哈希映射相同的数组。

让我们试运行一个例子。

arr={1,1,1,2,3,3,5,5,8,8,8,9,10}；

步骤1：从数组的每个元素中减去1

arr={0,0,0,1,2,2,4,4,7,7,8,9}

第2步：-将n添加到当前数组元素指向的索引中。

例如：-

当i=0时，arr[arr[0]%n]=0向arr[0]加n，arr[0]=14；

当i=1时，arr[arr[1]%n]=14加n到arr[0]，arr[0]=28；

同样地，用同样的方法找到修改后的数组，我们将得到如下数组：

arr={42,14,28,1,30,2,4,46,35,21,7,8,8,9}

第3步：-现在进入第2步，如果您注意到我们将n值添加到特定元素指向的索引中。如果我们不止一次有一个元素指向同一个索引，那么在这种情况下，修改后的数字除以 N 给我们数字的频率。

例如

i=0时；arr[0]=42；arr[0]/n=3这意味着0在修改后的数组中出现了三次，如步骤1的arr所示。

i=1时；arr[1]=14；arr[1]/14=1这意味着1在修改后的数组中出现了一次，正如您在步骤1的arr中看到的那样。

同样，对于其他我们可以计算的值。

C++

                         // C++ program to count number of occurrences of                       
                         // each element in the array #include <iostream>                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // It prints number of occurrences of each element in the                       
                         // array.                       
                         void                                     findFrequency(                                     int                                     input[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 input[i]--;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 input[input[i] % n] += n;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (input[i] / n)                       
                                                 cout <<                                     "Element "                                     << (i + 1) <<                                     " occurs "                       
                                                 << input[i] / n <<                                     " times"                                     << endl;                       
                                                 // Change the element back to original value                       
                                                 input[i] = input[i] % n + 1;                       
                                                 }                       
                         }                       
           
                         // Driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[]                       
                                                 = { 1, 1, 1, 2, 3, 3, 5, 5, 8, 8, 8, 9, 9, 10 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 findFrequency(arr, n);                       
           
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by aditya kumar(adiyakumar129)                       

JAVA

                         // Java program to count number of occurrences of each                       
                         // element in the array                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
                         class                                     GFG {                       
           
                                                 // It prints number of occurrences of each element in                       
                                                 // the array.                       
                                                 static                                     void                                     findFrequency(                                     int                                     [] input,                                     int                                     n)                       
                                                 {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 input[i]--;                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 input[input[i] % n] += n;                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     ((input[i] / n) !=                                     0                                     )                       
                                                 System.out.println(                       
                                                 "Element "                                     + (i +                                     1                                     ) +                                     " occurs "                       
                                                 + input[i] / n +                                     " times"                                     );                       
                                                 // Change the element back to original value                       
                                                 input[i] = input[i] % n +                                     1                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     [] arr                       
                                                 = {                                     1                                     ,                                     1                                     ,                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     3                                     ,                                     5                                     ,                                     5                                     ,                                     8                                     ,                                     8                                     ,                                     8                                     ,                                     9                                     ,                                     9                                     ,                                     10                                     };                       
                                                 int                                     n = arr.length;                       
                                                 findFrequency(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by aditya kumar(adiyakumar129)                       

C#

                         // C# program to count number of occurrences of each element                       
                         // in the array                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
           
                                                 // It prints number of occurrences of each element in                       
                                                 // the array.                       
                                                 static                                     void                                     findFrequency(                                     int                                     [] input,                                     int                                     n)                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 input[i]--;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 input[input[i] % n] += n;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     ((input[i] / n) != 0)                       
                                                 Console.WriteLine(                       
                                                 "Element "                                     + (i + 1) +                                     " occurs "                       
                                                 + input[i] / n +                                     " times"                                     );                       
                                                 // Change the element back to original value                       
                                                 input[i] = input[i] % n + 1;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver function                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     [] arr                       
                                                 = { 1, 1, 1, 2, 3, 3, 5, 5, 8, 8, 8, 9, 9, 10 };                       
                                                 int                                     n = arr.Length;                       
                                                 findFrequency(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by shikhasingrajput                       

Javascript

                         <script>                       
                         // Javascript program to count number of occurrences of                       
                         // each element in the array                       
           
                         // It prints number of                       
                         // occurrences of each element in the array.                       
                         function                                     findFrequency(input, n)                       
                         {                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 input[i]--;                       
           
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 input[input[i] % n] += n;                       
           
                                                 console.log(input)                       
                                                 for                                     (let i = 0; i < n; i++) {                       
                                                 if                                     (Math.floor(input[i] / n))                       
                                                 document.write(                                     "Element "                                     + (i + 1) +                       
                                                 " occurs "                                     + Math.floor(input[i] / n) +                                     " times <br>"                                     );                       
                                   
                                                 // Change the element back to original value                       
                                                 input[i] = input[i] % n + 1;                       
                                                 }                       
                         }                       
           
                         // Driver function                       
                         let arr = [1, 1, 1, 2, 3, 3, 5, 5, 8, 8, 8, 9, 9, 10];                       
                         let n = arr.length;                       
           
                         findFrequency(arr, n);                       
           
                         // This code is contributed by Saurabh Jaiswal                       
                         </script>                       

输出

Element 1 occurs 3 timesElement 2 occurs 1 timesElement 3 occurs 2 timesElement 5 occurs 2 timesElement 8 occurs 3 timesElement 9 occurs 2 timesElement 10 occurs 1 times

https://youtu.be/B2hI-QPoisk 本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章