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

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

例子：

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