Максимално разстояние между две появи на един и същ елемент в масива


Ниво на трудност M
Често задавани в Делхейвъри FactSet Фанатиците Fourkites
Array Хашиш

Да предположим, че сте получили масив с някои повтарящи се числа. Трябва да намерим максималното разстояние между двете едни и същи числа на число с различен индекс, присъстващо в масив.

Пример

Вход:

масив = [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 се съхранява в 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

Анализ на сложността за максимално разстояние между две появи на един и същ елемент в масива

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

О (п) където "н" е броят на елементите в масива.

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

О (п) където "н" е броят на елементите в масива.