అర్రే యొక్క అన్ని ఎలిమెంట్లను ఒకేలా చేయడానికి కనీస తొలగింపు ఆపరేషన్లు


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe ఫాక్ట్‌సెట్
అర్రే హాష్

మనకు ఇన్పుట్ ఉందని అనుకుందాం అమరిక తో "X" మూలకాల సంఖ్య. మేము తొలగింపు కార్యకలాపాలను కనుగొనవలసిన సమస్యను ఇచ్చాము, ఇది సమాన శ్రేణిని చేయడానికి అవసరమైన కనీసంగా ఉండాలి, అంటే శ్రేణి సమాన అంశాలను కలిగి ఉంటుంది.

ఉదాహరణ

ఇన్పుట్:

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

అవుట్పుట్:

3

వివరణ:

(4, 6, 2) 3 మూలకాలను తొలగించిన తరువాత, శ్రేణి సమానంగా మారుతుంది, [1, 1, 1]

ఇన్పుట్:

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

అవుట్పుట్:

5

వివరణ:

సమాన శ్రేణిగా మార్చడానికి మేము 5 మూలకాలలో దేనినైనా తీసివేయవచ్చు.

అల్గారిథం

  1. శ్రేణి యొక్క అన్ని మూలకాల యొక్క పౌన encies పున్యాలను మ్యాప్‌లో నిల్వ చేయండి.
  2. సెట్ “Max_freq” కు INT_MIN.
  3. మ్యాప్‌లో మళ్ళించండి మరియు గరిష్ట ఫ్రీక్వెన్సీ ఏ మూలకానికి ఉందో తనిఖీ చేయండి.
    • సెట్ “Max_freq” కు గరిష్టంగా (max_freq, విలువ) అన్ని పౌన .పున్యాల మధ్య గరిష్ట విలువను కనుగొనడానికి.
  4. శ్రేణి పరిమాణం మధ్య వ్యత్యాసాన్ని తిరిగి ఇవ్వండి “N” మరియు max_freq (n - max_freq).

వివరణ

మేము ఒక సమస్యను ఇచ్చాము, దీనిలో మనం ఎన్ని కనిష్టాలను కనుగొనాలి తొలగింపు శ్రేణిని సమానంగా చేయడానికి ఆపరేషన్లు అవసరం (సారూప్య మూలకాలతో). దీని కోసం, మేము నిల్వ చేయడానికి మ్యాప్‌ను ఉపయోగించబోతున్నాము పౌనఃపున్యాల శ్రేణిలో ఉన్న ప్రతి సంఖ్య.

ఇలా చేయడం ద్వారా, మనకు అన్ని పౌన .పున్యాలలో అతి పెద్ద ఫ్రీక్వెన్సీ ఉంటుంది. మ్యాప్‌లో మళ్ళించడం ద్వారా, గరిష్ట పద్ధతిని ఉపయోగించడం ద్వారా మేము ఆ గరిష్ట పౌన frequency పున్యాన్ని పొందవచ్చు. మళ్ళించిన తరువాత చిహ్నం మనకు గరిష్ట పౌన frequency పున్యం ఉంటుంది మరియు మేము శ్రేణి_ పరిమాణాన్ని తిరిగి ఇవ్వాలి - గరిష్ట పౌన frequency పున్యం, దీని అర్ధం శ్రేణిని సమానంగా చేయడానికి తొలగించగల తక్కువ పౌన encies పున్యాల సంఖ్యను మేము తిరిగి ఇస్తున్నాము.

ఒక ఉదాహరణను పరిశీలిద్దాం:

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 [r] ను 4 గా తీసుకుంటుంది, ఎందుకంటే 4 కి ఇప్పటికే మ్యాప్‌లో చోటు ఉంది, ఇది 4 యొక్క ముఖ్య స్థలంలో మరో గణనను జోడిస్తుంది మరియు ఫ్రీక్ (2, XNUMX) ని నిల్వ చేస్తుంది.
  • i = 4, ఇది arr [i] ను 2 గా తీసుకుంటుంది మరియు ఫ్రీక్ (2, 1) ని నిల్వ చేస్తుంది.
  • i = 5 కొరకు, ఇది 4 గా అర్ర్ [i] ను తీసుకుంటుంది, ఎందుకంటే 4 కి ఇప్పటికే మ్యాప్‌లో చోటు ఉంది, ఇది 4 యొక్క ముఖ్య స్థలంలో మరో గణనను జోడిస్తుంది మరియు ఫ్రీక్ (4, 3) ని నిల్వ చేస్తుంది.

వీటన్నిటిలో '4' గరిష్ట పౌన frequency పున్యం 3, మరియు మ్యాప్ నుండి గరిష్ట పౌన frequency పున్యాన్ని 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” శ్రేణిలోని మూలకాల సంఖ్య