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


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது சிட்டாடல் ஃபேப் ஃபோர்கைட்டுகள் Roblox டெஸ்லா
அணி ஹாஷ் வரிசையாக்க

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

உதாரணமாக

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

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2

விளக்கம்

1 → 3 அதிர்வெண் (அதிக அதிர்வெண்)

5 → 1 அதிர்வெண் (குறைந்த அதிர்வெண்)

arr[] = {5, 4, 5, 5, 5, 3, 4 }
3

விளக்கம்

5 → 4 அதிர்வெண் (அதிக அதிர்வெண்)

3 → 1 அதிர்வெண் (குறைந்த அதிர்வெண்)

அல்காரிதம்

  1. ஒரு அறிவிக்கவும் வரைபடம்.
  2. ஒரு வரிசை உறுப்பின் அதிர்வெண்ணை சேமித்து எண்ணவும்.
  3. தொகுப்பு maxfreq to 0 மற்றும் minfreq க்கு n.
  4. வரைபடத்தில் பயணிக்கவும்:
    1. வரைபடத்தில் மாக்ஸ்ஃப்ரெக் மற்றும் அதிர்வெண் இடையே அதிகபட்ச மதிப்பைக் கண்டுபிடித்து அதை மேக்ஸ்ஃப்ரெக்கில் சேமிக்கவும்.
    2. வரைபடத்தில் உள்ள minfreq க்கும் அதிர்வெண்ணிற்கும் இடையிலான குறைந்தபட்ச மதிப்பைக் கண்டுபிடித்து minfreq இல் சேமிக்கவும்.
  5. திரும்பவும் (maxfreq-minfreq).

விளக்கம்

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

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

ஒரு உதாரணத்தை எடுத்துக் கொள்வோம்:

உதாரணமாக

arr [] = {1, 2, 3, 1, 5, 2, 3, 1}

நாம் முதலில் வரிசைக்குச் செல்லும்போது, ​​உறுப்பு மற்றும் அவற்றின் நிகழ்வுகள் எதுவும் வரைபடத்தில் வைப்போம், பயணித்தபின் வரைபடத்தை இவ்வாறு வைத்திருப்போம்:

வரைபடம்: {1: 3, 2: 2, 3: 2, 5: 1}

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

  • 1: 3

3 மேக்ஸ்ஃப்ரெக்கை விட அதிகமாக உள்ளது, எனவே மேக்ஸ்ஃப்ரெக் = 3

3 minfreq ஐ விட சிறியது, எனவே minfreq = 3

  • 2: 2

maxfreq 2 ஐ விட அதிகமாக உள்ளது, எனவே maxfreq = 3

2 minfreq ஐ விட சிறியது, எனவே minfreq = 2

  • 3: 2

maxfreq 2 ஐ விட அதிகமாக உள்ளது, எனவே maxfreq = 3

Minfreq, minfreq = 2 இல் எதுவும் மாற்றப்படவில்லை

  • 5: 1

maxfreq 1 ஐ விட அதிகமாக உள்ளது, எனவே maxfreq = 3

1 minfreq ஐ விட சிறியது, எனவே minfreq = 1

மேலும் maxfreq-minfreq between (3-1) = 2 க்கு இடையிலான வித்தியாசத்தை நாங்கள் திருப்பித் தருகிறோம்.

குறியீடு

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

#include<iostream>
#include<unordered_map>

using namespace std;

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

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

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

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = 0 ; i < n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i], freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i], 1);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

சிக்கலான பகுப்பாய்வு

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

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. இங்கே நாம் வெறுமனே வரிசையின் கூறுகளை அவற்றின் அதிர்வெண்களைக் கண்காணிக்கிறோம். இவை அனைத்தும் O (N) நேரம் மட்டுமே செலவாகும்.

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

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. அதிகபட்சம், அவை அனைத்தும் வேறுபட்டால் நாம் n கூறுகளை சேமிக்க முடியும். விண்வெளி சிக்கலானது நேரியல்.