അറേയുടെ എല്ലാ ഘടകങ്ങളും തുല്യമാക്കുന്നതിനുള്ള പ്രവർത്തനങ്ങൾ‌ ഇല്ലാതാക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ഫാക്റ്റ്സെറ്റ്
അറേ ഹാഷ്

ഞങ്ങൾക്ക് ഒരു ഇൻപുട്ട് ഉണ്ടെന്ന് കരുതുക ശ്രേണി കൂടെ "എക്സ്" ഘടകങ്ങളുടെ എണ്ണം. ഇല്ലാതാക്കൽ പ്രവർത്തനങ്ങൾ കണ്ടെത്തേണ്ട ഒരു പ്രശ്നം ഞങ്ങൾ നൽകിയിട്ടുണ്ട്, അത് ഒരു തുല്യ അറേ നിർമ്മിക്കാൻ ആവശ്യമായ ഏറ്റവും കുറഞ്ഞതായിരിക്കണം, അതായത്, അറേയിൽ തുല്യ ഘടകങ്ങൾ അടങ്ങിയിരിക്കും.

ഉദാഹരണം

ഇൻപുട്ട്:

[1, 1, 4, 6, 2, 1]

ഔട്ട്പുട്ട്:

3

വിശദീകരണം:

(4, 6, 2) 3 ഘടകങ്ങൾ നീക്കം ചെയ്തതിനുശേഷം, അറേ തുല്യമാകും, [1, 1, 1]

ഇൻപുട്ട്:

[1, 5, 4, 16, 32, 9]

ഔട്ട്പുട്ട്:

5

വിശദീകരണം:

ഒരു തുല്യ അറേ ആക്കുന്നതിന് നമുക്ക് 5 ഘടകങ്ങളിൽ ഏതെങ്കിലും നീക്കംചെയ്യാം.

അൽഗോരിതം

  1. അറേയിലെ എല്ലാ ഘടകങ്ങളുടെയും ആവൃത്തി ഒരു മാപ്പിൽ സംഭരിക്കുക.
  2. ഗണം “പരമാവധി_ഫ്രെക്ക്” ലേക്ക് INT_MIN.
  3. മാപ്പിന് മുകളിലൂടെ ആവർത്തിച്ച് ഏത് ഘടകത്തിന് പരമാവധി ആവൃത്തി ഉണ്ടെന്ന് പരിശോധിക്കുക.
    • ഗണം “പരമാവധി_ഫ്രെക്ക്” ലേക്ക് പരമാവധി (പരമാവധി_ഫ്രെക്ക്, മൂല്യം) എല്ലാ ആവൃത്തികൾക്കിടയിലും പരമാവധി മൂല്യം കണ്ടെത്തുന്നതിന്.
  4. അറേ വലുപ്പം തമ്മിലുള്ള വ്യത്യാസം നൽകുക “N” ഒപ്പം max_freq (n - max_freq).

വിശദീകരണം

ഞങ്ങൾ‌ ഒരു പ്രശ്‌നം നൽ‌കി, അതിൽ‌ എത്ര മിനിമം ഉണ്ടെന്ന് കണ്ടെത്തേണ്ടതുണ്ട് ഇല്ലാതാക്കൽ ഒരു ശ്രേണി തുല്യമാക്കുന്നതിന് (സമാന ഘടകങ്ങളുടെ) പ്രവർത്തനങ്ങൾ ആവശ്യമാണ്. ഇതിനായി, സംഭരിക്കാൻ ഞങ്ങൾ ഒരു മാപ്പ് ഉപയോഗിക്കാൻ പോകുന്നു ആവൃത്തികൾ അറേയിലുള്ള ഓരോ സംഖ്യയുടെയും.

ഇത് ചെയ്യുന്നതിലൂടെ, ആ ആവൃത്തി നമുക്ക് ലഭിക്കും, അത് എല്ലാ ആവൃത്തികളിൽ ഏറ്റവും വലുതാണ്. മാപ്പിലൂടെ ആവർത്തിക്കുന്നതിലൂടെ, പരമാവധി രീതി ഉപയോഗിച്ച് നമുക്ക് ആ പരമാവധി ആവൃത്തി നേടാനാകും. ആവർത്തനത്തിനുശേഷം ഭൂപടം ഞങ്ങൾക്ക് പരമാവധി ആവൃത്തി ഉണ്ടായിരിക്കും, കൂടാതെ ഞങ്ങൾ അറേ_സൈസ് - പരമാവധി ഫ്രീക്വൻസി നൽകേണ്ടതുണ്ട്, അതിനർത്ഥം അറേ തുല്യമാക്കുന്നതിന് നീക്കംചെയ്യാനാകുന്ന കുറഞ്ഞ ഫ്രീക്വൻസികളുടെ എണ്ണം ഞങ്ങൾ നൽകുന്നുവെന്നാണ്.

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം:

arr: {10, 3, 4, 4, 2, 4};

  • i = 0, ഇതിന് arr [i] 10 ആയി എടുക്കുകയും ഫ്രീക്ക് (10, 1) സംഭരിക്കുകയും ചെയ്യുന്നു.
  • i = 1, ഇതിന് arr [i] 3 ആയി എടുക്കുകയും ഫ്രീക്ക് (3, 1) സംഭരിക്കുകയും ചെയ്യുന്നു.
  • i = 2 ന്, ഇത് arr [i] നെ 4 ആയി എടുക്കുകയും ഫ്രീക്ക് (4, 1) സംഭരിക്കുകയും ചെയ്യുന്നു.
  • i = 3, ഇത് 4 ആയി എടുക്കുന്നു, കാരണം 4 ന് ഇതിനകം ഒരു മാപ്പിൽ ഒരു സ്ഥാനം ഉള്ളതിനാൽ ഇത് 4 ന്റെ പ്രധാന സ്ഥലത്ത് ഒരു എണ്ണം കൂടി ചേർത്ത് ഫ്രീക്ക് (4, 2) സംഭരിക്കുക.
  • i = 4, ഇത് arr [i] നെ 2 ആയി എടുക്കുകയും ഫ്രീക്ക് (2, 1) സംഭരിക്കുകയും ചെയ്യുന്നു.
  • i = 5 ന്, ഇത് 4 ആയി എടുക്കുന്നു, കാരണം 4 ന് ഇതിനകം ഒരു മാപ്പിൽ ഒരു സ്ഥാനം ഉള്ളതിനാൽ ഇത് 4 ന്റെ പ്രധാന സ്ഥലത്ത് ഒരു എണ്ണം കൂടി ചേർത്ത് ഫ്രീക്ക് (4, 3) സംഭരിക്കുക.

ഇവയിൽ '4' എന്ന സംഖ്യയ്ക്ക് പരമാവധി ആവൃത്തി 3 ആണ്, മാപ്പിൽ നിന്ന് പരമാവധി ആവൃത്തി 3 ആയി സഞ്ചരിച്ച് കണ്ടെത്തിയതിന് ശേഷം, ഞങ്ങൾ മൂല്യം തിരികെ നൽകാൻ പോകുന്നു (n - max_freq) 3. അതാണ് ഞങ്ങളുടെ .ട്ട്‌പുട്ട്.

നടപ്പിലാക്കൽ

അറേയുടെ എല്ലാ ഘടകങ്ങളും തുല്യമാക്കുന്നതിന് മിനിമം ഡിലീറ്റ് ഓപ്പറേഷനുകൾക്കായുള്ള സി ++ പ്രോഗ്രാം

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

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

    int max_freq = INT_MIN;

    for (auto itr = freq.begin(); itr != freq.end(); itr++)
        max_freq = max(max_freq, itr->second);

    return n - max_freq;
}
int main()
{
    int arr[] = { 10, 3, 4, 4, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minDelete(arr, n);
    return 0;
}
3

അറേയുടെ എല്ലാ ഘടകങ്ങളും തുല്യമാക്കുന്നതിന് മിനിമം ഡിലീറ്റ് ഓപ്പറേഷനുകൾക്കായുള്ള ജാവ പ്രോഗ്രാം

import java.util.HashMap;
class minimumDeletionOperation
{
    public static int noOfMinimumDeletions(int arr[], int n)
    {
        HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
        for(int i=0; i<arr.length; i++)
        {
            if(freq.containsKey(arr[i]))
                freq.put(arr[i], freq.get(arr[i]) + 1);
            else
                freq.put(arr[i], 1);
        }

        int max_freq=Integer.MIN_VALUE;

        for (int i:freq.keySet())
            max_freq = Math.max(max_freq, freq.get(i));

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

അറേയുടെ എല്ലാ ഘടകങ്ങളും തുല്യമാക്കുന്നതിന് മിനിമം ഡിലീറ്റ് ഓപ്പറേഷനുകൾക്കായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം