അറേയിലെ ഒരേ മൂലകത്തിന്റെ രണ്ട് സംഭവങ്ങൾക്കിടയിലുള്ള പരമാവധി ദൂരം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ദില്ലി ഫാക്റ്റ്സെറ്റ് ഫനാറ്റിക്സ് ഫോർകൈറ്റുകൾ
അറേ ഹാഷ്

നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് കരുതുക ശ്രേണി ആവർത്തിച്ചുള്ള ചില സംഖ്യകളോടെ. ഒരു ശ്രേണിയിൽ നിലവിലുള്ള വ്യത്യസ്ത സൂചികയുള്ള ഒരു സംഖ്യയുടെ രണ്ട് സമാന സംഭവങ്ങൾ തമ്മിലുള്ള പരമാവധി ദൂരം ഞങ്ങൾ കണ്ടെത്തണം.

ഉദാഹരണം

ഇൻപുട്ട്:

അറേ = [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. ഒരു പ്രഖ്യാപിക്കുക ഭൂപടം.
  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 മാക്സ് ഡിസ്റ്റൻസിൽ സംഭരിച്ചിരിക്കുന്നു.

ഞങ്ങൾ മാക്സ് ഡിസ്റ്റൻസ് 9 ആയി നൽകുന്നു.

നടപ്പിലാക്കൽ

അറേയിലെ ഒരേ ഘടകത്തിന്റെ രണ്ട് സംഭവങ്ങൾക്കിടയിലുള്ള പരമാവധി ദൂരത്തിനായുള്ള സി ++ പ്രോഗ്രാം

#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

അറേയിലെ ഒരേ മൂലകത്തിന്റെ രണ്ട് സംഭവങ്ങൾക്കിടയിലുള്ള പരമാവധി ദൂരത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം

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

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

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

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