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


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அகோலைட் அமேசான் உயர்வு மேக்மைட்ரிப் ஓலா கேப்ஸ் SAP ஆய்வகங்கள்
அணி ஹாஷ்

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

உதாரணமாக

arr[] =  {2, 3, 5, 1, 4, 6, 2, 5};
6

விளக்கம்

2 இன் முதல் குறியீட்டு → 0

2 இன் கடைசி குறியீட்டு → 6

அதிகபட்ச வேறுபாடு (6-0) = 6

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

arr[] =  {2, 3, 6, 5, 4, 5, 1, 4};
3

விளக்கம்

4 இன் முதல் குறியீட்டு → 4

4 இன் கடைசி குறியீட்டு → 7

அதிகபட்ச வேறுபாடு (7-4) = 3

அல்காரிதம்

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

விளக்கம்

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

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

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

உதாரணமாக

அர் [] = {2, 3, 5, 1, 4, 6, 2, 5}

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

வரைபடம்: 1-> 3: பூஜ்ய,

2-> 0: 6,

3-> 1, பூஜ்ய,

4-> 4: பூஜ்ய,

5-> 2: 7,

6-> 5: பூஜ்ய

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

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

#include<bits/stdc++.h>

using namespace std;

int maxDifference(int arr[], int n)
{
    struct IndexValue
    {
        int fir, last;
    };
    unordered_map<int, IndexValue> MAP;
    for (int i=0; i<n; i++)
    {
        if (MAP.find(arr[i]) == MAP.end())
            MAP[arr[i]].fir = i;

        MAP[arr[i]].last = i;
    }

    int difference, differenceIndex = INT_MIN;

    unordered_map<int, IndexValue>::iterator itr;
    for (itr=MAP.begin(); itr != MAP.end(); itr++)
    {
        difference = (itr->second).last - (itr->second).fir;
        if (differenceIndex < difference)
            differenceIndex = difference;
    }
    return differenceIndex;
}
int main()
{
    int arr[] = {2, 3, 5, 1, 4, 6, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference b/w the first and last index of a number= "<<maxDifference(arr, n);
    return 0;
}
Maximum difference b/w the first and last index of a number= 6

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

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

class IndexValue
{
    int first;
    int second;
    public IndexValue()
    {
        super();
    }
}
class DifferenceOfIndexes
{
    private static int getIndexesDifferent(int[] arr)
    {
        int n = arr.length;
        int differenceIndex = 0;
        Map<Integer, IndexValue> MAP = new HashMap<Integer, IndexValue>();

        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]))
            {
                IndexValue iv = MAP.get(arr[i]);
                iv.second = i;
            }
            else
            {
                IndexValue iv = new IndexValue();
                iv.first = i;
                MAP.put(arr[i], iv);
            }
        }
        for (Map.Entry<Integer, IndexValue> entry : MAP.entrySet())
        {
            IndexValue iv = entry.getValue();
            if ((iv.second - iv.first) > differenceIndex)
            {
                differenceIndex = iv.second - iv.first;
            }
        }
        return differenceIndex;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,5,1,4,6,2,5};
        System.out.println("Maximum difference b/w the first and last index of a number= "+ getIndexesDifferent(arr));
    }
}
Maximum difference b/w the first and last index of a number= 6

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

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

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

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

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