Масофаи максималӣ байни ду рухдоди як унсур дар массив


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Деҳлӣ Factset Фараж Фуркайтҳо
тартиботи ҳарбӣ Хаш

Фарз мекунем, ки ба шумо ан асал бо баъзе рақамҳои такрорӣ. Мо бояд масофаи максималии байни ду падидаи якхелаи ададро бо индекси гуногун, ки дар массив мавҷуд аст, ёбем.

мисол

Қайд:

массиви = [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. маҷмӯи "MaxDistance" ба 0.
  3. Дар ҳоле ки ман аз дарозии массив (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 дар maxDistance нигоҳ дошта мешавад.

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

Таҳлили мураккабӣ барои масофаи максималии байни ду рухдоди як унсур дар массив

Мураккабии вақт

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.