Максимална удаљеност између два појављивања истог елемента у низу


Ниво тешкоће Средњи
Често питани у Делхивери Фацтсет Фанатици Фоуркитес
Ред Хасх

Претпоставимо да вам је дато поредак са неким поновљеним бројевима. Морамо да пронађемо максималну удаљеност између две исте појаве броја са различитим индексом, присутног у низу.

Пример

Улаз:

низ = [1, 2, 3, 6, 2, 7]

Излаз:

3

objašnjenje:

Јер елементи у низу [1] и низу [4] имају исте елементе који су „2“ са максималном удаљеностом од 3.

Улаз:

низ = [3, 4, 6, 7, 4, 8, 9, 3]

Излаз:

7

objašnjenje:

Јер низ елемената [0] и низ [7] имају исте елементе који су '3' са максималном удаљеностом од 3.

Алгоритам за максималну удаљеност између два појављивања истог елемента

  1. Изјавите а Мапа.
  2. Сет “МакДистанце” да КСНУМКС.
  3. Док је и мања од дужине низа (н).
    1. Проверите сваки елемент низа да ли се први пут појављује или не на мапи, ако је први,
      1. Затим ставите елемент и његов индекс на мапу.
    2. Иначе (ако већ постоји)
      1. Пронађите максималну удаљеност између претходне и ове (удаљеност између индекса).
      2. Чувајте максималну удаљеност до “МакДистанце”.
  4. повратак “МакДистанце”.

Објашњење

Дали смо низ са неколико поновљених елемената у њему. Наш задатак је да откријемо максималну разлику између положаја истих појављивања броја. За ово ћемо користити мапу. На тој мапи ћемо ставити елементе низа као кључ, а њихов индекс као вредност. Тада ћемо пронаћи максималну разлику или растојање између два индекса истог броја ако постоји, мада треба да нађемо растојање између истих елемената.

На мапи сваки кључ има неку вредност као елемент низа и њихови индекси, ако су за сваки елемент пронађена два индекса, тада ћемо пронаћи разлику између тих индекса и наћи већу разлику између претходних “МакДистанце” и ово садашње. А онда, након итерације по целом низу имамо највећу максималну удаљеност.

Размотримо пример:

Пример

арр [] = {8, 1, 3, 2, 4, 1, 3, 6, 7, 3, 1};

и = 0, арр [и] = 8 => моја карта = {8: 0}

и = 1, арр [и] = 1 => моја карта = {8: 0, 1: 1}

и = 2, арр [и] = 3 => моја карта = {8: 0, 1: 1, 3: 2}

и = 3, арр [и] = 2 => миМап = {8: 0, 1: 1, 3: 2, 2: 3}

и = 4, арр [и] = 4 => миМап = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}

и = 5, арр [и] = 1 => миМап = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}, Овде ће наћи разлику између садашњег индекса и претходног индекса '1', (5-1 = 4), 4 се чува у макДистанце.

и = 6, арр [и] = 3 => миМап = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4} Овде ће наћи разлику између садашњег индекса и претходног индекса ' 3 ', (6-2 = 4), али 4 је већ у макДистанце, па није важно.

и = 7, арр [и] = 6 => миМап = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7}

и = 8, арр [и] = 7 => миМап = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8}

и = 9, арр [и] = 3 => миМап = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} Овде ће наћи разлику између садашњи индекс и претходни индекс '3', (9-3 = 6), 6 се чувају у макДистанце.

и = 10, арр [и] = 3 => миМап = {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

Анализа сложености за максималну удаљеност између два појављивања истог елемента у низу

Сложеност времена

Он) где „Н“ је број елемената у низу.

Сложеност простора

Он) где „Н“ је број елемената у низу.