வரிசையின் அனைத்து கூறுகளையும் ஒரே மாதிரியாக மாற்ற குறைந்தபட்ச நீக்குதல் செயல்பாடுகள்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் உண்மை
அணி ஹாஷ்

எங்களிடம் உள்ளீடு உள்ளது என்று வைத்துக்கொள்வோம் வரிசை உடன் "எக்ஸ்" உறுப்புகளின் எண்ணிக்கை. நீக்குதல் செயல்பாடுகளை நாம் கண்டுபிடிக்க வேண்டிய ஒரு சிக்கலை நாங்கள் கொடுத்துள்ளோம், இது ஒரு சமமான வரிசையை உருவாக்க குறைந்தபட்சமாக இருக்க வேண்டும், அதாவது வரிசை சம உறுப்புகளைக் கொண்டிருக்கும்.

உதாரணமாக

உள்ளீடு:

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

வெளியீடு:

3

விளக்கம்:

(4, 6, 2) 3 கூறுகளை அகற்றிய பின், வரிசை சமமாகிறது, அதாவது [1, 1, 1]

உள்ளீடு:

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

வெளியீடு:

5

விளக்கம்:

சமமான வரிசையாக மாற்ற 5 உறுப்புகளில் ஏதேனும் ஒன்றை நாம் அகற்றலாம்.

அல்காரிதம்

  1. வரிசையின் அனைத்து உறுப்புகளின் அதிர்வெண்களையும் ஒரு வரைபடத்தில் சேமிக்கவும்.
  2. தொகுப்பு “Max_freq” க்கு INT_MIN.
  3. வரைபடத்தின் மீது சொடுக்கவும், எந்த உறுப்பு அதிகபட்ச அதிர்வெண் உள்ளது என்பதை சரிபார்க்கவும்.
    • தொகுப்பு “Max_freq” க்கு அதிகபட்சம் (max_freq, மதிப்பு) எல்லா அதிர்வெண்களிலும் அதிகபட்ச மதிப்பைக் கண்டறிய.
  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, இது ar [i] ஐ 4 ஆக எடுக்கும், 4 க்கு ஏற்கனவே ஒரு வரைபடத்தில் இடம் இருப்பதால், அது 4 இன் முக்கிய இடத்தில் மேலும் ஒரு எண்ணிக்கையைச் சேர்த்து, ஃப்ரீக் (4, 2) ஐ சேமிக்கிறது.
  • i = 4, இது arr [i] ஐ 2 ஆக எடுத்து, ஃப்ரீக்கை (2, 1) சேமிக்கிறது.
  • i = 5 க்கு, இது 4 ஆக ஆகிறது [4] ஒரு வரைபடத்தில் ஏற்கனவே 4 இடம் இருப்பதால், அது 4 இன் முக்கிய இடத்தில் மேலும் ஒரு எண்ணிக்கையைச் சேர்த்து, ஃப்ரீக் (3, XNUMX) ஐ சேமிக்கிறது.

இவை அனைத்திலும் '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

வரிசையின் அனைத்து கூறுகளையும் ஒரே மாதிரியாக மாற்ற குறைந்தபட்ச நீக்குதல் நடவடிக்கைகளுக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (ந) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை

விண்வெளி சிக்கலானது

ஓ (ந) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை