د دوه عناصرو د فریکونسۍ تر مینځ اعظمي توپیر لکه هغه عنصر چې لوړې فریکونسۍ لري هم خورا لوی دی  


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي Accenture اکولایټ ترلاسه کړئ Amazon VMware
پیشه هاش ترتیب کول

فرض کړئ ، تاسو یو عدد لرئ سور. د ستونزې بیان غوښتنه کوي چې د ورکړل شوي صفونو د دوو جلا عناصرو د فریکونسۍ تر مینځ اعظمي توپیر ومومئ ، مګر هغه عنصر چې د لوړې فریکونسۍ سره باید د نورو انټریر څخه هم ډیر وي.

بېلګه  

تفتیش:

تیر [] = {2,4,4,4,3,2،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

محصول:

2

وضاحت:

د 4 → 3 فریکوینسي

د 2 → 2 فریکوینسي

او د 3 → 1 فریکونسۍ

4 (3) - 3 (1) = 2 (انټیجر هم لوی او اعظمي فریکونسۍ دي).

الګوریتم  

  1. اعلامیه a نقشه او یو ځاې د اوږدوالي 'فاصله' وايي.
  2. حساب او زیرمه یې کړئ د عناصرو فریکونسي نخشه کې او په ورته وخت کې د صفونو ارزښتونه فاصله صف کې ذخیره کړئ.
  3. د واټن سرې ترتيب کړئ.
  4. لږترلږه n + 1 ته وټاکئ او 0 ته وتلو.
  5. صف ته ځیر شئ ، پداسې حال کې چې زه
    1. د محصول تر مینځ اعظمي حد ومومئ او د فاصلو د ارزښت تر مینځ توپیر ومومئ [i] او لږترلږه یې آؤټ کولو ته وساتئ.
    2. د لږترلږه او د واټن ارزښت تر مینځ لږترلږه ومومئ [i] او لږترلږه یې زیرمه کړئ.
  6. بیرته راګرځول.

تشریح  

موږ ته اعداد درکول کیږي او موږ باید د دوه عناصرو د فریکونسۍ تر مینځ اعظمي توپیر ومومو نو هغه عنصر چې لوی فریکونسۍ ولري باید د ټیټ فریکونسۍ سره د نورو انټریر څخه هم لوی وي او هم د لوی عدد څخه کم وي. موږ کارولو ته ځو ځورول او ډولونه کوم چې به موږ سره د مؤثره کوډ جوړولو کې مرسته وکړي. لومړی ، موږ به یوه نقشه او د عدد صف اعلان کړو چې ورته ورکړل شوي صف سره ورته اندازې سره فاصله ویل کیږي.

هم وګوره
د ګراف لپاره د لومړي لمبر لټون (BFS)

کله چې د صفونو عناصرو فریکونسۍ ذخیره کولو او شمیرلو لپاره د ارې تعقیب کول موږ هم اړتیا لرو زموږ د الګوریتم مطابق د سرنی [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

د دوو عناصرو د فریکونسۍ تر منځ د اعظمي توپیر لپاره د جاوا برنامې

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 نګ ن) هلته "n" په صف کې د عناصرو شمیر دی.

هم وګوره
په صف کې نزدې عناصر جلا کړئ

د ځای پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی.