അറേയിലെ ഒരു മൂലകത്തിന്റെ ആദ്യ, അവസാന സൂചികകൾ തമ്മിലുള്ള പരമാവധി വ്യത്യാസം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ ഉയർത്തൽ MakeMyTrip ഓല ക്യാബുകൾ എസ്എപി ലാബുകൾ
അറേ ഹാഷ്

നിങ്ങൾക്ക് ഒരു ഉണ്ടെന്ന് കരുതുക ശ്രേണി 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N ' അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N ' അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം