兩個元素的頻率之間的最大差異,使得具有更大頻率的元素也更大  


難度級別 中烘焙
經常問 埃森哲 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的整數數組,該數組的大小與給定數組的大小相同。

也可以看看
圖形的廣度優先搜索(BFS)

在遍歷數組以存儲和計算數組元素的頻率時,我們還需要根據我們的算法存儲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” 是數組中元素的數量。