Массивдеги бир эле элементтин эки көрүнүшүнүн ортосундагы максималдуу аралык


Кыйынчылык деңгээли орто
Көп суралган Delhivery Factset динчилдер Fourkites
согуштук тизме таштанды

Сизге ан берилген деп коёлу согуштук тизме кайталанган сандар менен. Массивде көрсөтүлгөн ар кандай индекстеги бирдей көрүнүштөрдүн ортосундагы максималдуу аралыкты табышыбыз керек.

мисал

киргизүү:

массив = [1, 2, 3, 6, 2, 7]

Output:

3

Explanation:

Массивдеги [1] жана массивдеги [4] элементтердин элементтери бирдей, '2' максималдуу аралык 3ке жетет.

киргизүү:

массив = [3, 4, 6, 7, 4, 8, 9, 3]

Output:

7

Explanation:

[0] жана [7] массив элементтеринин элементтери бирдей, '3', максималдуу аралык 3.

Бир эле элементтин эки пайда болушунун ортосундагы максималдуу аралыктын алгоритми

  1. Декларация a карта.
  2. коюлган “MaxDistance” 0 үчүн.
  3. Ал эми i (n) массивинин узундугунан аз.
    1. Массивдин ар бир элементинин биринчи пайда болгон-болбогонун текшерип, эгер картасында жок болсо,
      1. Андан кийин элементти жана анын индексин картага салыңыз.
    2. Башка (эгер ал бар болсо)
      1. Мурунку менен мунун ортосундагы эң чоң аралыкты билип алыңыз (индекстин ортосундагы аралык).
      2. Максималдуу аралыкты чейин сактаңыз “MaxDistance”.
  4. Return “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 буга чейин maxDistanceде болгондуктан, мааниге ээ эмес.

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 maxDistanceде сакталат.

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де сакталат.

Биз 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

Массивдеги бир эле элементтин эки жолугуусунун ортосундагы максималдуу аралык үчүн Java программасы

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" массивдеги элементтердин саны.