Максимальна відстань між двома появами одного елемента в масиві  


Рівень складності Medium
Часто запитують у Делівері Факти Фанатики Фуркіти
масив Мішанина

Припустимо, вам дано масив з деякими повторюваними числами. Ми повинні знайти максимальну відстань між двома однаковими входженнями числа з різним індексом, присутнього в масиві.

Приклад  

Вхідний сигнал:

масив = [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. Поки i менше довжини масиву (n).
    1. Перевірте кожен елемент масиву, якщо він вперше зустрічається чи ні на карті, якщо перший,
      1. Потім помістіть елемент та його індекс на карту.
    2. Інакше (якщо воно вже існує)
      1. З’ясуйте максимальну відстань між попередньою та цією (відстань між індексом).
      2. Зберігайте максимальну відстань до “MaxDistance”.
  4. Повертати “MaxDistance”.

Пояснення  

Ми дали масив з деякими повторюваними елементами в ньому. Наше завдання - з’ясувати максимальну різницю між положеннями однакових випадків числа. Для цього ми будемо використовувати карту. На цій карті ми будемо розміщувати елементи масиву як ключ, а їх індекс - як значення. Тоді ми збираємось знайти максимальну різницю або відстань між двома індексами одного і того ж числа, якщо воно існує, хоча нам потрібно знайти відстань між однаковими елементами.

Дивись також
Запити на XOR найбільшого непарного дільника діапазону

На карті кожен ключ має якесь значення як елемент масиву та їх індекси, якщо для кожного елемента знайдено два індекси, то ми знайдемо різницю між цими індексами та знайдемо більшу різницю між попередніми “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

Аналіз складності для максимальної відстані між двома появами одного елемента в масиві  

Складність часу

О (п) де "N" - кількість елементів у масиві.

Складність простору

О (п) де "N" - кількість елементів у масиві.