په صف کې د ورته عنصر د دوه پیښو تر مینځ اعظمي فاصله  


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي دهلي حقیقت انځورونه څلورکیټونه
پیشه هاش

فرض کړئ تاسو ته یو ورکړل شوی سور د یو شمیر تکرار شمېرو سره. موږ باید د مختلف شمیرو سره د ورته ورته دوه پیښو ترمینځ اعظمي فاصله ومومو ، چې په یوځای کې شتون لري.

بېلګه  

تفتیش:

سرنی = [1 ، 2 ، 3 ، 6 ، 2 ، 7]

محصول:

3

وضاحت:

ځکه چې په صفونو کې [1] او صف [[] کې عناصر ورته عنصرونه لري چې '4' د 2 د حد اکثر فاصلو سره.

تفتیش:

سرنی = [3 ، 4 ، 6 ، 7 ، 4 ، 8 ، 9 ، 3]

محصول:

7

وضاحت:

ځکه چې عنصر صف [0] او صف [7] ورته عنصرونه لري چې د 3 3 اعظمي فاصله سره 'XNUMX' دي.

د ورته عنصر د دوه پیښو تر مینځ د اعظمي فاصلي لپاره الګوریتم  

  1. اعلامیه a نقشه.
  2. ټاکل شوی "اعظمي فاصله" ته 0 ته.
  3. پداسې حال کې چې زه د صف له اوږدوالي څخه کم یم (n).
    1. هر صف عنصر چیک کړئ که چیرې دا لومړۍ پیښه ولري یا نه په نقشه کې ، که لومړی ،
      1. بیا عنصر او د دې شاخص په نقشه کې ولیکئ.
    2. نور (که دا دمخه شتون ولري)
      1. د تیر او دې یو تر مینځ اعظمي فاصله ومومئ (د شاخصونو ترمنځ واټن).
      2. تر اعظمي فاصله ذخیره کړئ "اعظمي فاصله".
  4. بیرته راګرځی "اعظمي فاصله".

تشریح  

موږ په دې کې د ځینې تکراري عناصرو سره صف ورکړی. زموږ دنده د یو شمیر ورته پیښو د موقعیت تر مینځ اعظمي توپیر موندلو لپاره دی. موږ به د دې لپاره نقشه وکاروو. پدې نقشه کې ، موږ د کلي عناصرو او د هغوی شاخص د ارزښت په توګه کیښودو. بیا موږ د ورته شمیرو دوه شاخصونو تر مینځ اعظمي توپیر یا فاصله ومومو که شتون ولري ، که څه هم موږ اړتیا لرو د ورته عناصرو ترمینځ فاصله ومومئ.

هم وګوره
د سلسلې ترټولو لوی عجيبه تقویم د XOR په اړه پوښتنې

په نقشه کې ، هر کلیدي پدې کې د سرې عنصر او د دوی شاخصونو کې یو څه ارزښت لري ، که چیرې د هر عنصر لپاره دوه شاخصونه وموندل شي ، نو بیا به موږ د دې شاخصونو تر مینځ توپیر ومومو او د تیر ترمینځ لوی توپیر ومومو "اعظمي فاصله" او اوسنی. او بیا د بشپړ صف څخه تکرار کولو وروسته موږ ترټولو لوی اعظمي فاصله لرو.

راځئ چې یوه بېلګه په نظر کې ونیسو:

بېلګه

تیر [] = {8 ، 1 ، 3 ، 2 ، 4 ، 1 ، 3 ، 6 ، 7 ، 3 ، 1}؛

i = 0 ، آر [i] = 8 => زما میپ = {8: 0}

i = 1 ، ارار [i] = 1 => زما میپ = {8: 0 ، 1: 1}

i = 2 ، تیر [i] = 3 => زما میپ = {8: 0 ، 1: 1 ، 3: 2}

i = 3 ، آر [i] = 2 => زما میپ = {8: 0 ، 1: 1 ، 3: 2 ، 2: 3}

i = 4 ، آر [i] = 4 => زما میپ = {8: 0 ، 1: 1 ، 3: 2 ، 2: 3 ، 4: 4}

i = 5 ، آر [i] = 1 => زما میپ = {8: 0 ، 1: 1 ، 3: 2 ، 2: 3 ، 4: 4 Here ، دلته به د موجود شاخص او پخوانۍ شاخص سره توپیر ومومي '1' ، (5-1 = 4) ، 4 په اعظمي فاصله کې ذخیره کیږي.

i = 6 ، آر [i] = 3 => زما میپ = {8: 0 ، 1: 1 ، 3: 2 ، 2: 3 ، 4: 4} دلته به د موجود شاخص او پخوانۍ شاخص سره توپیر ومومئ ' 3 '، (6-2 = 4) ، مګر 4 لا دمخه په مکسډ فاصله کې دی ، نو دا مسله نده.

i = 7 ، آر [i] = 6 => زما میپ = {8: 0 ، 1: 1 ، 3: 2 ، 2: 3 ، 4: 4 ، 6: 7}

i = 8 ، آر [i] = 7 => زما میپ = {8: 0 ، 1: 1 ، 3: 2 ، 2: 3 ، 4: 4 ، 6: 7 ، 7: 8}

i = 9 ، تیر [i] = 3 => زما میپ = {8: 0 ، 1: 1 ، 3: 2 ، 2: 3 ، 4: 4 ، 6: 7 ، 7: 8} دلته به دا توپیر ومومي اوسنی شاخص او د '3' پخوانۍ شاخص ، (9-3 = 6) ، 6 په مکس ډیټنس کې ذخیره ده.

i = 10 ، تیر [i] = 3 => زما میپ = {8: 0 ، 1: 1 ، 3: 2 ، 2: 3 ، 4: 4 ، 6: 7 ، 7: 8} دلته به دا توپیر ومومي اوسنی شاخص او د '1' پخوانۍ شاخص ، (10-1 = 9) ، 9 په مکس ډیټنس کې ذخیره ده.

هم وګوره
د میټریکس ډیجنل سم لیټکوډ حل

او موږ د 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" په صف کې د عناصرو شمیر دی.

د ځای پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی.