数组中最高频率和最低频率的区别

假设给定一个数组，找出数组中任何数字的最高出现次数和最低出现次数。

例子：

Input  : arr[] = [7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5] Output : 2 Lowest occurring element (5) occurs once. Highest occurring element (1 or 7) occurs 3 times  Input  : arr[] = [1, 1, 1, 3, 3, 3] Output : 0 

一个简单的解决方案是使用两个循环来计算每个元素的频率并跟踪最大和最小频率。更好的解决方案是在 O(n log n) 中对数组进行排序并检查连续元素的出现并分别比较它们的计数。
C++实现：

// CPP code to find the difference between highest // and least frequencies #include <bits/stdc++.h> using namespace std;  int findDiff(int arr[], int n) {     // sort the array     sort(arr, arr + n);      int count = 0, max_count = 0, min_count = n;     for (int i = 0; i < (n - 1); i++) {          // checking consecutive elements         if (arr[i] == arr[i + 1]) {             count += 1;             continue;         }         else {             max_count = max(max_count, count);             min_count = min(min_count, count);             count = 0;         }     }      return (max_count - min_count); }  // Driver code int main() {     int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };     int n = sizeof(arr) / sizeof(arr[0]);      cout << findDiff(arr, n) << "n";     return 0; } 

Java实现：

// JAVA Code for Difference between // highest and least frequencies // in an array import java.util.*;  class GFG {      static int findDiff(int arr[], int n)     {         // sort the array         Arrays.sort(arr);          int count = 0, max_count = 0,             min_count = n;          for (int i = 0; i < (n - 1); i++) {              // checking consecutive elements             if (arr[i] == arr[i + 1]) {                 count += 1;                 continue;             }             else {                 max_count = Math.max(max_count,                                     count);                  min_count = Math.min(min_count,                                     count);                 count = 0;             }         }          return (max_count - min_count);     }      // Driver program to test above function     public static void main(String[] args)     {          int arr[] = { 7, 8, 4, 5, 4, 1,                     1, 7, 7, 2, 5 };         int n = arr.length;          System.out.println(findDiff(arr, n));     } }  // This code is contributed by Arnav Kr. Mandal. 

运行结果如下：

2 

一个有效的解决方案是使用散列。计算所有元素的频率，最后遍历哈希表找到最大值和最小值。
参考下面是代码实现：

C++实现

// CPP code to find the difference between highest // and least frequencies #include <bits/stdc++.h> using namespace std;  int findDiff(int arr[], int n) {     // Put all elements in a hash map     unordered_map<int, int> hm;     for (int i = 0; i < n; i++)         hm[arr[i]]++;      // Find counts of maximum and minimum     // frequent elements     int max_count = 0, min_count = n;     for (auto x : hm) {         max_count = max(max_count, x.second);         min_count = min(min_count, x.second);     }      return (max_count - min_count); }  // Driver int main() {     int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };     int n = sizeof(arr) / sizeof(arr[0]);      cout << findDiff(arr, n) << "n";     return 0; } 

Java实现

// Java code to find the difference between highest // and least frequencies import java.util.*;  class GFG {  static int findDiff(int arr[], int n) {     // Put all elements in a hash map     Map<Integer,Integer> mp = new HashMap<>();     for (int i = 0 ; i < n; i++)     {         if(mp.containsKey(arr[i]))         {             mp.put(arr[i], mp.get(arr[i])+1);         }         else         {             mp.put(arr[i], 1);         }     }      // Find counts of maximum and minimum     // frequent elements     int max_count = 0, min_count = n;     for (Map.Entry<Integer,Integer> x : mp.entrySet())     {         max_count = Math.max(max_count, x.getValue());         min_count = Math.min(min_count, x.getValue());     }      return (max_count - min_count); }  // Driver code public static void main(String[] args) {     int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };     int n = arr.length;     System.out.println(findDiff(arr, n)); } }  /* This code is contributed by PrinciRaj1992 */ 

运行结果如下：

2