חילוק צווישן העכסטן און קלענסטער פריקוואַנסיז אין אַ מענגע  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין ציטאַדעל Fab פאָורקיטעס ראָבלאָקס טעסלאַ
מענגע האַש סאָרטינג

די פּראָבלעם "דיפעראַנסיז צווישן העכסטן און קלענסטער פריקוואַנסיז אין אַ מענגע" שטאַטן אַז רעכן איר האָבן אַן ינטעגער מענגע. די פּראָבלעם ויסזאָגונג איז צו געפֿינען די מאַקסימום חילוק צווישן די העכסטן אָפטקייַט און לאָואַסט אָפטקייַט פון צוויי פאַרשידענע נומערן אין אַ מענגע.

בייַשפּיל  

חילוק צווישן העכסטן און קלענסטער פריקוואַנסיז אין אַ מענגעשפּילקע

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2

דערקלערונג

אָפטקייַט פון 1 → 3 (העכסטן אָפטקייַט)

אָפטקייַט פון 5 → 1 (לאָואַסט אָפטקייַט)

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

דערקלערונג

אָפטקייַט פון 5 → 4 (העכסטן אָפטקייַט)

אָפטקייַט פון 3 → 1 (לאָואַסט אָפטקייַט)

אַלגאָריטהם  

  1. דערקלערן א מאַפּע.
  2. קראָם און ציילן די אָפטקייַט פון אַ מענגע עלעמענט.
  3. שטעלן maxfreq צו 0 און מינפרעק צו n.
  4. דורכפאָר די מאַפּע:
    1. געפֿינען די מאַקסימום ווערט צווישן מאַקספרעק און אָפטקייַט אין די מאַפּע און סטאָרד עס צו מאַקספרעק.
    2. געפֿינען די מינימום ווערט צווישן די מינפראַק און אָפטקייַט אין די מאַפּע און קראָם עס צו מינפראַק.
  5. צוריקקער (maxfreq-minfreq).

דערקלערונג

מיר האָבן אַ מענגע פון ​​ינטאַדזשערז. אונדזער אַרבעט איז צו געפֿינען די מאַקסימום חילוק צווישן די העכסטן פּאַסירונג און די לאָואַסט פּאַסירונג פון צוויי פאַרשידענע נומערן אין אַ מענגע. מיר וועלן נוצן כאַשינג. האַשינג גיט אַן עפעקטיוו וועג צו סאָלווע די קשיא. מיר וועלן דערקלערן אַ מאַפּע און ציילן די פריקוואַנסיז פון יעדער מענגע עלעמענט און סיימאַלטייניאַסלי סטאָרד די פרעקווענסיעס מיט די עלעמענטן אין דער מאַפּע.

זע אויך
דרוק אַלע סובאַררייַס מיט 0 סומע

דערנאָך מיר שטעלן די ווערט פון maxfreq צו 0 און מינפרעק צו n, הייסט, די לענג פון די מענגע ווייַל קיין עלעמענט האט אַ אָפטקייַט גרעסער ווי די גרייס פון דעם געגעבן מענגע. מיר וועלן דורכגיין די מאַפּע און קלייַבן יעדער עלעמענט איינער פֿאַר איינער און קאָנטראָלירן אויב עס איז די גרעסטע אָדער לאָואַסט אָפטקייַט. באַזונדער די מאַקסימום אָפטקייַט צו אַ אַנדערש בייַטעוודיק און מינימום אָפטקייַט צו פאַרשידענע בייַטעוודיק. מיר דאַרפֿן צו ווייַזן די חילוק צווישן די מאַקסימום אָפטקייַט און די לאָואַסט אָפטקייַט, אַזוי מיר וועלן צוריקקומען (maxfreq-minfreq).

לאָמיר נעמען אַ ביישפּיל:

בייַשפּיל

arr [] = {1, 2, 3, 1, 5, 2, 3, 1}

ווען מיר ערשטער פאָרן די מענגע, מיר שטעלן דעם עלעמענט און זייער נומער פון געשעענישן אין די מאַפּע, און נאָך די דורכפאָר מיר האָבן די מאַפּע ווי:

מאפע: {1: 3, 2: 2, 3: 2, 5: 1}

איצט, מיר האָבן די פֿאַלן פון יעדער עלעמענט אין דער מאַפּע, מיר וועלן אַריבער די מאַפּע און קלייַבן יעדער עלעמענט פֿון דער מאַפּע און קאָנטראָלירן זייער אָפטקייַט, וואָס איז די גרעסערע קראַנט אָפטקייַט אָדער מאַקספרעק און וואָס איז די מינימום קראַנט אָפטקייַט אָדער מינפרעק און קראָם עס צו מאַקספרעק און מינפרעק ריספּעקטיוולי.

  • 1: 3 →

3 איז גרעסער ווי maxfreq, אַזוי maxfreq = 3

3 איז קלענערער ווי מינפראַק, אַזוי מינפרעק = 3

  • 2: 2 →

מאַקספרעק איז גרעסער ווי 2, אַזוי מאַקספרעק = 3

2 איז קלענערער ווי מינפראַק, אַזוי מינפרעק = 2

  • 3: 2 →

מאַקספרעק איז גרעסער ווי 2, אַזוי מאַקספרעק = 3

גאָרנישט איז געביטן אין מינפרעק, מינפרעק = 2

  • 5: 1 →

מאַקספרעק איז גרעסער ווי 1, אַזוי מאַקספרעק = 3

1 איז קלענערער ווי מינפראַק, אַזוי מינפרעק = 1

זע אויך
געמעל פענס אַלגערידאַם

און מיר וועלן צוריקקומען די חילוק צווישן maxfreq-minfreq → (3-1) = 2.

קאָדעקס  

C ++ קאָד צו געפֿינען דיפעראַנסיז צווישן העכסטן און קלענסטער פריקוואַנסיז אין אַ מענגע

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumDiff(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

Java קאָד צו געפֿינען דיפעראַנסיז צווישן די העכסטן און קלענסטער פריקוואַנסיז אין אַ מענגע

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = 0 ; i < n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i], freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i], 1);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין די מענגע. דאָ מיר האָבן סימפּלי דורכגעקאָכט די עלעמענטן פון די מענגע מיט אַ שפּור פון זייער פריקוואַנסיז. דאָס קאָס בלויז צייט O (N).

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין די מענגע. אין רובֿ, מיר קענען קראָם ע עלעמענטן אויב אַלע פון ​​זיי זענען אַנדערש. די פּלאַץ קאַמפּלעקסיטי איז לינעאַר.