శ్రేణిలో ఒకే మూలకం యొక్క రెండు సంఘటనల మధ్య గరిష్ట దూరం


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Delhivery ఫాక్ట్‌సెట్ ఇష్టపడేవారిని ఫోర్కైట్స్
అర్రే హాష్

మీకు ఒక ఇవ్వబడింది అనుకుందాం అమరిక కొన్ని పునరావృత సంఖ్యలతో. శ్రేణిలో ఉన్న వేర్వేరు సూచికలతో సంఖ్య యొక్క రెండు ఒకే సంఘటనల మధ్య గరిష్ట దూరాన్ని మనం కనుగొనాలి.

ఉదాహరణ

ఇన్పుట్:

శ్రేణి = [1, 2, 3, 6, 2, 7]

అవుట్పుట్:

3

వివరణ:

ఎందుకంటే శ్రేణి [1] మరియు శ్రేణి [4] లోని మూలకాలు గరిష్టంగా 2 దూరంతో '3' మూలకాలను కలిగి ఉంటాయి.

ఇన్పుట్:

శ్రేణి = [3, 4, 6, 7, 4, 8, 9, 3]

అవుట్పుట్:

7

వివరణ:

ఎందుకంటే మూలకం శ్రేణి [0] మరియు శ్రేణి [7] ఒకే మూలకాలను కలిగి ఉంటాయి, ఇవి గరిష్టంగా 3 దూరంతో '3'.

ఒకే మూలకం యొక్క రెండు సంఘటనల మధ్య గరిష్ట దూరం కోసం అల్గోరిథం

  1. ప్రకటించండి a చిహ్నం.
  2. సెట్ “మాక్స్ డిస్టాన్స్” 0 కు.
  3. నేను శ్రేణి (n) యొక్క పొడవు కంటే తక్కువగా ఉండగా.
    1. ప్రతి శ్రేణి మూలకం దాని మొదటి సంఘటన ఉందా లేదా మ్యాప్‌లో ఉందా అని తనిఖీ చేయండి, మొదట ఉంటే,
      1. అప్పుడు మూలకం మరియు దాని సూచికను మ్యాప్‌లో ఉంచండి.
    2. లేకపోతే (ఇది ఇప్పటికే ఉంటే)
      1. మునుపటి మరియు ఈ మధ్య గరిష్ట దూరాన్ని కనుగొనండి (సూచిక మధ్య దూరం).
      2. గరిష్ట దూరాన్ని నిల్వ చేయండి “మాక్స్ డిస్టాన్స్”.
  4. రిటర్న్ “మాక్స్ డిస్టాన్స్”.

వివరణ

మేము దానిలో కొన్ని పునరావృత అంశాలతో శ్రేణిని ఇచ్చాము. సంఖ్య యొక్క ఒకే సంఘటనల స్థానం మధ్య గరిష్ట వ్యత్యాసాన్ని కనుగొనడం మా పని. దీని కోసం మేము ఒక మ్యాప్‌ను ఉపయోగించబోతున్నాము. ఆ మ్యాప్‌లో, మేము శ్రేణి మూలకాలను కీగా మరియు వాటి సూచికను విలువగా ఉంచబోతున్నాము. ఒకే సంఖ్య యొక్క రెండు సూచికల మధ్య ఉన్న గరిష్ట వ్యత్యాసం లేదా దూరాన్ని మనం కనుగొంటాము, అయినప్పటికీ ఒకే మూలకాల మధ్య దూరాన్ని మనం కనుగొనవలసి ఉంటుంది.

ఒక మ్యాప్‌లో, ప్రతి కీలో శ్రేణి యొక్క మూలకం మరియు వాటి సూచికలుగా కొంత విలువ ఉంటుంది, ప్రతి మూలకానికి రెండు సూచికలు కనుగొనబడితే, అప్పుడు మేము ఆ సూచికల మధ్య వ్యత్యాసాన్ని కనుగొని మునుపటి మధ్య పెద్ద వ్యత్యాసాన్ని కనుగొనబోతున్నాము “మాక్స్ డిస్టాన్స్” మరియు ప్రస్తుత ఒకటి. ఆపై మొత్తం శ్రేణిపై మళ్ళించిన తరువాత మనకు అతిపెద్ద గరిష్ట దూరం ఉంది.

ఒక ఉదాహరణను పరిశీలిద్దాం:

ఉదాహరణ

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

i = 0, arr [i] = 8 => myMap = {8: 0}

i = 1, arr [i] = 1 => myMap = {8: 0, 1: 1}

i = 2, arr [i] = 3 => myMap = {8: 0, 1: 1, 3: 2}

i = 3, arr [i] = 2 => myMap = {8: 0, 1: 1, 3: 2, 2: 3}

i = 4, arr [i] = 4 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}

i = 5, arr [i] = 1 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}, ఇక్కడ ఇది ప్రస్తుత సూచిక మరియు మునుపటి సూచిక మధ్య వ్యత్యాసాన్ని కనుగొంటుంది '1', (5-1 = 4), 4 మాక్స్ డిస్టాన్స్‌లో స్టోర్.

i = 6, arr [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4} ఇక్కడ ఇది ప్రస్తుత సూచిక మరియు మునుపటి సూచిక మధ్య వ్యత్యాసాన్ని కనుగొంటుంది. 3 ', (6-2 = 4), కానీ 4 ఇప్పటికే మాక్స్ డిస్టాన్స్‌లో ఉంది, కాబట్టి ఇది పట్టింపు లేదు.

i = 7, arr [i] = 6 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7}

i = 8, arr [i] = 7 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8}

i = 9, arr [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} ఇక్కడ ఇది మధ్య వ్యత్యాసాన్ని కనుగొంటుంది ప్రస్తుత సూచిక మరియు మునుపటి సూచిక '3', (9-3 = 6), 6 మాక్స్డిస్టెన్స్లో స్టోర్.

i = 10, arr [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} ఇక్కడ ఇది మధ్య వ్యత్యాసాన్ని కనుగొంటుంది ప్రస్తుత సూచిక మరియు మునుపటి సూచిక '1', (10-1 = 9), 9 మాక్స్డిస్టెన్స్లో స్టోర్.

మరియు మేము maxDistance ను 9 గా తిరిగి ఇస్తాము.

అమలు

శ్రేణిలో ఒకే మూలకం యొక్క రెండు సంఘటనల మధ్య గరిష్ట దూరం కోసం C ++ ప్రోగ్రామ్

#include<bits/stdc++.h>
using namespace std;

int getDistance(int arr[], int n)
{
    unordered_map<int, int> my_map;
    int maxDistance = 0;
    for (int i=0; i<n; i++)
    {
        if (my_map.find(arr[i]) == my_map.end())
            my_map[arr[i]] = i;
        else
            maxDistance = max(maxDistance, i - my_map[arr[i]]);
    }

    return maxDistance;
}
int main()
{
    int arr[] = {8, 1, 3, 2, 4, 1, 3, 6, 7, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getDistance(arr, n);
    return 0;
}
9

శ్రేణిలో ఒకే మూలకం యొక్క రెండు సంఘటనల మధ్య గరిష్ట దూరం కోసం జావా ప్రోగ్రామ్

import java.io.*;
import java.util.*;

class distanceBSameNumbers
{
    static int getDistance(int[] arr, int n)
    {
        HashMap<Integer,Integer> my_map = new HashMap<>();

        int maxDistance = 0;

        for (int i = 0; i < n; i++)
        {
            if (!my_map.containsKey(arr[i]))
                my_map.put(arr[i], i);

            else
                maxDistance = Math.max(maxDistance, i - my_map.get(arr[i]));
        }

        return maxDistance;
    }
    public static void main(String args[])
    {
        int arr[] = {8,1,3,2,4,1,3,6,7,3,1};
        int n = arr.length;
        System.out.println(getDistance(arr, n));
    }
}
9

శ్రేణిలో ఒకే మూలకం యొక్క రెండు సంఘటనల మధ్య గరిష్ట దూరం కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై)  (ఇక్కడ “N” శ్రేణిలోని మూలకాల సంఖ్య.

అంతరిక్ష సంక్లిష్టత

పై)  (ఇక్కడ “N” శ్రేణిలోని మూలకాల సంఖ్య.