Առավելագույն հեռավորությունը զանգվածում նույն տարրի երկու դեպքերի միջև


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Առաքում Փաստեր Ֆանատիկա Ֆուրկիտներ
Դասավորություն Խանգարել

Ենթադրենք, որ ձեզ տրված է դասավորություն որոշ կրկնվող թվերով: Մենք պետք է գտնենք առավելագույն հեռավորությունը զանգվածի մեջ առկա տարբեր ցուցիչով թվերի երկու նույն դեպքերի միջև:

Օրինակ

Մուտք:

զանգված = [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. հավաքածու «MaxDistance» Ինչպես 0:
  3. Մինչդեռ i- ն պակաս է զանգվածի (n) երկարությունից:
    1. Ստուգեք յուրաքանչյուր զանգվածի տարրը, եթե այն ունի իր առաջին դեպքը, թե ոչ քարտեզում, եթե առաջինը,
      1. Դրանից հետո տարրը և դրա ինդեքսը դրեք քարտեզի մեջ:
    2. Այլ (եթե այն արդեն գոյություն ունի)
      1. Պարզեք նախորդի և այս մեկի առավելագույն հեռավորությունը (հեռավորությունը ինդեքսի միջև):
      2. Պահպանեք առավելագույն հեռավորությունը մինչև «MaxDistance».
  4. Վերադառնալ «MaxDistance».

բացատրություն

Մենք զանգված ենք տվել, որի մեջ կան մի քանի կրկնվող տարրեր: Մեր խնդիրն է պարզել համարի նույն դեպքերի դիրքի առավելագույն տարբերությունը: Դրա համար մենք պատրաստվում ենք օգտագործել քարտեզ: Այդ քարտեզում մենք զանգվածի տարրերը դնելու ենք որպես բանալի, իսկ դրանց ինդեքսը ՝ որպես արժեք: Այդ դեպքում մենք կգտնենք նույն թվի երկու ցուցանիշների առավելագույն տարբերությունը կամ հեռավորությունը, եթե դա գոյություն ունի, չնայած պետք է գտնել նույն տարրերի միջև հեռավորությունը:

Քարտեզում յուրաքանչյուր ստեղն իր մեջ որոշակի արժեք ունի որպես զանգվածի տարր և դրանց ինդեքսներ, եթե յուրաքանչյուր տարրի համար կա երկու ինդեքս, ապա մենք կգտնենք այդ ցուցանիշների տարբերությունը և ավելի մեծ տարբերություն կգտնենք նախորդի միջև: «MaxDistance» իսկ ներկան: Եվ հետո ամբողջ զանգվածը կրկնելուց հետո մենք ունենք ամենամեծ առավելագույն հեռավորությունը:

Քննենք մի օրինակ.

Օրինակ

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

Programավային ծրագիր զանգվածում նույն տարրի երկու դեպքերի միջև առավելագույն հեռավորության համար

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

Բարդության վերլուծություն զանգվածում նույն տարրի երկու դեպքերի միջև առավելագույն հեռավորության համար

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: