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


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் கருப்பு பாறை சிட்டாடல் டைரக்டி , Flipkart உண்மையில் யாண்டேக்ஸ்
அணி ஹேஷிங்

“எல்லா உறுப்புகளையும் வரிசையில் சமமாக்குவதற்கான குறைந்தபட்ச செயல்பாடு” என்ற சிக்கல் உங்களுக்கு வழங்கப்பட்டுள்ளது என்று கூறுகிறது வரிசை சிலருடன் முழு அதில் உள்ளது. ஒரு வரிசையை சமமாக்குவதற்கு செய்யக்கூடிய குறைந்தபட்ச செயல்பாடுகளை நீங்கள் கண்டுபிடிக்க வேண்டும்.

உதாரணமாக  

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

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

விளக்கம்

ஒன்று 3 கழிப்புகளைச் செய்யலாம் அல்லது 3 சேர்த்தல்களைச் செய்ய முடியும்.

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

விளக்கம்

ஒன்று 4 கழிப்புகளைச் செய்யலாம் அல்லது 4 சேர்த்தல்களைச் செய்ய முடியும்.

அனைத்து கூறுகளையும் சமமாக்குவதற்கு குறைந்தபட்ச செயல்பாடுகளைக் கண்டறிய வழிமுறை  

  1. ஒரு அறிவிக்கவும் வரைபடம்.
  2. நான் <n போது, ​​வளைய தொடர்கிறது
    1. ஒவ்வொரு உறுப்புக்கும் வரிசை உறுப்பு மற்றும் அதிர்வெண்களை வரைபடத்தில் சேமிக்கவும்.
  3. தொகுப்பு “அதிகபட்ச எண்ணிக்கை” 0 வரை.
  4. என்பதை சரிபார்க்கவும் “அதிகபட்ச எண்ணிக்கை” வரைபடத்தில் விசையின் மதிப்பை விட குறைவாக உள்ளது
    1. நிபந்தனை திருப்தி அடைந்தால், அமைக்கவும் “அதிகபட்ச எண்ணிக்கை” விசையின் மதிப்புக்கு.
  5. திரும்பவும் (n - “maxCount”).

விளக்கம்

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

மேலும் காண்க
பைனரி தேடல் மரம் செயல்பாட்டை நீக்கு

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

இங்கே ஒரு உதாரணத்தைக் கருத்தில் கொள்வோம்:

உதாரணமாக

arr: {1, 5, 2, 1, 3, 2, 1};

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

i = 0,

arr [i] = 1

countFreq = [1: 1]

நான் = 1

arr [i] = 5

countFreq = [1: 1,5: 1]

நான் = 2

arr [i] = 2

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

நான் = 3

arr [i] = 1

countFreq = [1: 2,5: 1,2: 1] => இங்கே “1” என்ற உறுப்பை இரண்டு முறை கண்டுபிடிப்போம், எனவே 1 இன் அதிர்வெண் எண்ணிக்கையை அதிகரிக்கும்.

நான் = 4

arr [i] = 3

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

நான் = 5

arr [i] = 2

countFreq = [1: 2,5: 1,2: 2: 3: 1] => இங்கே “2” என்ற உறுப்பை இரண்டு முறை கண்டுபிடிப்போம், எனவே 2 இன் அதிர்வெண் எண்ணிக்கையை அதிகரிக்கும்.

நான் = 6

arr [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => இங்கே “1” என்ற உறுப்பை மூன்று முறை கண்டுபிடிப்போம், எனவே 1 இன் அதிர்வெண் எண்ணிக்கையை அதிகரிக்கும்.

இப்போது துவக்கவும் “அதிகபட்ச எண்ணிக்கை” to 0. மேலும் ஒவ்வொரு அதிர்வெண்ணையும் விட அதிகமாக இருந்தால் சரிபார்க்கவும் “அதிகபட்ச எண்ணிக்கை”, அதிகமாக இருப்பதைக் கண்டால், அந்த அதிர்வெண்ணின் மதிப்பை சேமிக்கவும் “அதிகபட்ச எண்ணிக்கை”

கடைசியாக, மிகப் பெரிய அதிர்வெண் நமக்கு இருக்கும் “அதிகபட்ச எண்ணிக்கை”.

நாங்கள் n- “அதிகபட்ச எண்ணிக்கை” => 7-3 = 4, அதாவது வரிசையை சமமாக்குவதற்கு குறைந்தபட்சம் 4 செயல்பாடுகளைச் செய்ய வேண்டும்.

குறியீடு  

அனைத்து உறுப்புகளையும் வரிசையில் சமமாக்குவதற்கு குறைந்தபட்ச செயல்பாட்டைக் கண்டுபிடிக்க சி ++

#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” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.