两个元素的频率之间的最大差异,使得具有更大频率的元素也更大


难度级别 中等
经常问 Accenture ol石 亚马逊 VMware的
排列 哈希 排序

假设您有一个整数 排列。 问题陈述要求找出给定数组的任何两个不同元素的频率之间的最大差异,但频率较高的元素的值也应大于其他整数。

使用案列

输入:

arr [] = {2,4,4,4,3,2}

输出:

2

说明:

频率4→3

频率2→2

频率为3→1

4(3)– 3(1)= 2(整数也更大且为最大频率)。

算法

  1. 声明一个 地图 数组说长度为n的“距离”。
  2. 计算并存储 元素频率 到地图中,同时将数组的值存储到距离数组中。
  3. 对距离数组进行排序。
  4. 将最小值设置为n + 1并输出为0。
  5. 遍历数组,而我
    1. 找到输出之间的最大值和距离[i]的值与最小值之间的差,并将其存储到输出中。
    2. 在最小值和距离[i]的值之间找到最小值,并将其存储到最小值。
  6. 返回输出。

说明

我们给定一个整数,我们需要找出两个元素的频率之间的最大差,以使具有更高频率的元素也应该大于另一个具有最低频率的整数,并且还小于一个更大的整数。 我们将要使用 哈希 以及 排序 这将有助于我们编写高效的代码。 首先,我们将声明一个映射和一个名为distance的整数数组,该数组的大小与给定数组的大小相同。

在遍历数组以存储和计算数组元素的频率时,我们还需要根据我们的算法存储array [i]的值。 我们将输出值设置为0,最小值设置为n + 1。 这个最小值有助于我们找出所有频率中的最小值,然后在输出变量中存储最大值。 现在,我们需要对存储值的数组进行排序(距离数组)。

我们现在将遍历距离数组,并且需要遍历到值j,因为在上一个遍历中,当我们将值存储在距离中时,我们在增加j的值,因此j的值是该距离的最大值要遍历的数组。 我们需要找到输出之间的最大距离以及频率和最小值之间的差。 并将其存储为输出,我们还需要找到距离数组元素的最小值和频率之间的最小值并将其存储为最小值。 这将继续下去,直到遍历距离数组中的所有值为止。 最后,我们在输出中找到最合适的答案,然后我们将返回该输出值。

实施

C ++程序,用于两个元素的频率之间的最大差

#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;

int getMaximumDifference(int arr[], int n)
{
    unordered_map<int, int> freq;

    int distance[n];
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (freq.find(arr[i]) == freq.end())
            distance[j++] = arr[i];

        freq[arr[i]]++;
    }
    sort(distance, distance + j);

    int minimum = n+1;

    int output = 0;
    for (int i=0; i<j; i++)
    {
        int currentFrequency = freq[distance[i]];
        output = max(output, currentFrequency - minimum);
        minimum = min(minimum, currentFrequency);
    }

    return output;
}
int main()
{
    int arr[] = {2,4,4,4,3,2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaximumDifference(arr, n) << endl;
    return 0;
}
2

Java程序,用于两个元素的频率之间的最大差

import java.util.HashMap;
import java.util.Arrays;
class maximumDifferenceFrequency
{
    public static int getMaximumDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> frequency=new HashMap<>();

        int distance[]=new int[n];
        int j = 0;
        for (int i = 0; i < n; i++)
        {
            if (frequency.containsKey(arr[i]))
            {
                frequency.put(arr[i],frequency.get(arr[i])+1);

            }
            else
            {
                frequency.put(arr[i],1);
            }
            distance[j++] = arr[i];
        }
        Arrays.sort(distance);

        int minimum = n+1;

        int output = 0;
        for (int i=0; i<j; i++)
        {
            int currentFrequency = frequency.get(distance[i]);
            output = Math.max(output, currentFrequency - minimum);
            minimum = Math.min(minimum, currentFrequency);
        }

        return output;
    }
    public static void main(String [] args)
    {
        int arr[] = {2,4,4,4,3,2};
        int n = arr.length;

        System.out.println(getMaximumDifference(arr, n));
    }
}
2

复杂度分析,两个元素的频率之间存在最大差异

时间复杂度

O(n log n) 哪里 “ n” 是数组中元素的数量。

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。