מינימום אָפּעראַציע צו מאַכן אַלע יסודות גלייַך אין מענגע  


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

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

בייַשפּיל  

מינימום אָפּעראַציע צו מאַכן אַלע יסודות גלייַך אין מענגע

[ 1,3,2,4,1]
3

דערקלערונג

אָדער 3 סאַבטראַקשאַנז קענען זיין געטאן אָדער 3 אַדישאַנז צו מאַכן אַן גלייַך מענגע.

[5,3,2,4,1]
4

דערקלערונג

אָדער 4 סאַבטראַקשאַנז קענען זיין געטאן אָדער 4 אַדישאַנז צו מאַכן אַן גלייַך מענגע.

אַלגערידאַם צו געפֿינען מינימום אַפּעריישאַנז צו מאַכן אַלע עלעמענטן גלייַך  

  1. דערקלערן א מאַפּע.
  2. בשעת איך <n, שלייף האלט
    1. קראָם די מענגע עלעמענט און פריקוואַנסיז פון יעדער עלעמענט אין דער מאַפּע.
  3. שטעלן “MaxCount” צו קסנומקס.
  4. יטעראַטינג איבער די שלייף טשעק אויב “MaxCount” איז ווייניקער ווי די ווערט פון שליסל אין אַ מאַפּע
    1. אויב די צושטאַנד סאַטיספייז, שטעלן די “MaxCount” צו שליסל ס ווערט.
  5. ווייַזן (n - "maxCount").

דערקלערונג

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

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

זע אויך
ביינערי זוכן בוים ויסמעקן אָפּעראַציע

לאָמיר באַטראַכטן אַ ביישפּיל דאָ:

בייַשפּיל

אַרר: {1, 5, 2, 1, 3, 2, 1};

סטאַרטינג פון דער ערשטער מערסט עלעמענט, מיר טראַסעס די גאנצע מענגע און ציילן די אָפטקייַט פון יעדער עלעמענט און סטאָרד עס צו די מאַפּע.

איך = 0,

אַרר [איך] = 1

קאַונטפרעק = [1: 1]

איך = קסנומקס

אַרר [איך] = 5

קאַונטפרעק = [1: 1,5: 1]

איך = קסנומקס

אַרר [איך] = 2

קאַונטפרעק = [1: 1,5: 1,2: 1]

איך = קסנומקס

אַרר [איך] = 1

countFreq = [1: 2,5: 1,2: 1] => דאָ מיר וועלן געפֿינען די עלעמענט “1” צוויי מאָל אַזוי אַז די אָפטקייַט ציילן פון 1 וועט פאַרגרעסערן.

איך = קסנומקס

אַרר [איך] = 3

countFreq=[1:2,5:1,2:1,3:1]

איך = קסנומקס

אַרר [איך] = 2

countFreq = [1: 2,5: 1,2: 2: 3: 1] => דאָ מיר וועלן געפֿינען די עלעמענט “2” צוויי מאָל אַזוי אַז די אָפטקייַט ציילן פון 2 וועט פאַרגרעסערן.

איך = קסנומקס

אַרר [איך] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => דאָ מיר וועלן געפֿינען די עלעמענט "1" דרייַ מאָל, אַזוי דאָס וועט פאַרגרעסערן די אָפטקייַט פון 1.

איצט יניטיאַליזירן “MaxCount” צו 0. און טשעק פֿאַר יעדער אָפטקייַט אויב עס איז גרעסער ווי “MaxCount”, אויב עס וועט זיין גרעסערע, סטאָרד די ווערט פון די אָפטקייַט צו “MaxCount”

לעסאָף מיר וועלן האָבן די גרעסטע אָפטקייַט אין “MaxCount”.

מיר צוריקקומען N- “MaxCount” => 7-3 = 4, דאָס איז, מיר זאָל מאַכן מינימום פון 4 אַפּעריישאַנז צו מאַכן די מענגע גלייַך.

קאָדעקס  

C ++ צו געפֿינען מינימום אָפּעראַציע צו מאַכן אַלע יסודות גלייַך אין מענגע

#include <bits/stdc++.h>
using namespace std;

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

  int maxCount = 0;
  for (auto i : countFreq)
    if (maxCount < i.second)
      maxCount = i.second;

  return (n - maxCount);
}
int main()
{
  int arr[] = {1, 5, 2, 1, 3, 2, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << getMinimumOperation(arr, n);
  return 0;
}
4

דזשאַוואַ קאָד צו געפֿינען מינימום אָפּעראַציע צו מאַכן אַלע יסודות גלייַך אין מענגע

import java.util.*;
class minimumOperations
{
    public static int getMinimumOperations(int arr[], int n)
    {
        HashMap<Integer, Integer> countFreq = new HashMap<Integer, Integer>();

        for (int i=0; i<n; i++)
        {
            if(countFreq.containsKey(arr[i]))
            {
                countFreq.put(arr[i], countFreq.get(arr[i])+1);
            }
            else
            {
                countFreq.put(arr[i], 1);
            }
        }
        int maxCount = 0;

        Set<Integer> s = countFreq.keySet();

        for (int i : s)
            if (maxCount < countFreq.get(i))
                maxCount = countFreq.get(i);


        return (n - maxCount);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 5, 2, 1, 3, 2, 1};
        int n = arr.length;
        System.out.println(getMinimumOperations(arr, n));
    }
}
4

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

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

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע.

זע אויך
געפֿינען פּערז מיט אַ געגעבן סומע אַזוי אַז עלעמענטן פון פּאָר זענען אין פאַרשידענע ראָוז

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

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע.