Максимальная разница между первым и последним индексами элемента в массиве


Сложный уровень средний
Часто спрашивают в Акколит Амазонка Поход MakeMyTrip Ола Кабс SAP Labs
массив Hash

Предположим, у вас есть массив of целые. Задача «Максимальная разница между первым и последним индексами элемента в массиве» просит определить разницу между первым и последним индексами каждого числа, присутствующего в массиве, чтобы разница была максимальной.

Пример

arr[] =  {2, 3, 5, 1, 4, 6, 2, 5};
6

объяснение

Первый индекс 2 → 0

Последний индекс 2 → 6

Максимальная разница (6-0) = 6

Максимальная разница между первым и последним индексами элемента в массиве

arr[] =  {2, 3, 6, 5, 4, 5, 1, 4};
3

объяснение

Первый индекс 4 → 4

Последний индекс 4 → 7

Максимальная разница (7-4) = 3

Алгоритм

  1. Пройдите через все массив.
  2. Выберите каждый элемент массива, получите его первый и последний элемент и сохраните его в HashTable.
  3. Пройдите через карта:
    1. Узнайте разницу между первым и последним индексом каждого элемента.
    2. Сохраните максимальную разницу в какой-либо переменной и продолжайте обновлять ее всякий раз, когда найдете максимальное значение, чем предыдущее значение.
  4. Верните максимальную разницу.

объяснение

Нам дается целое array, нам нужно выяснить разницу между первым индексом и последним индексом каждого значения массива. Найдите максимальную разницу для любого числа между его первым и последним индексом. Для этого мы будем использовать хеширования. Мы возьмем элемент массива и узнаем его первый индекс и последний индекс или когда он встречается первым и последним.

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

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

Пример

Arr [] = {2, 3, 5, 1, 4, 6, 2, 5}

У нас есть входной массив. Чтобы решить эту проблему, мы воспользуемся классом. Мы будем искать каждый элемент, если он проходит впервые. Затем мы сохраним его индекс как первый индекс и когда тот же элемент появится снова. Затем каждый раз мы будем сохранять его индекс как второй индекс. Используя этот метод, мы получаем карту как:

Карта: 1-> 3: ноль,

2-> 0: 6,

3-> 1, ноль,

4-> 4: ноль,

5-> 2: 7,

6-> 5: ноль

Мы пройдемся по карте, возьмем каждое значение и проверим различия их индексов. Мы собираемся пренебречь всеми значениями, имеющими нулевые значения. Итак, у нас есть 2 и 5, из которых 2 имеет максимальную разницу (6) между первым и последним индексами, чем 5 имеющее отличие (5). Итак, мы вернем 6 как максимальную разницу, и это будет нашим ответом.

Код C ++ для поиска максимальной разницы между первым и последним индексами элемента в массиве

#include<bits/stdc++.h>

using namespace std;

int maxDifference(int arr[], int n)
{
    struct IndexValue
    {
        int fir, last;
    };
    unordered_map<int, IndexValue> MAP;
    for (int i=0; i<n; i++)
    {
        if (MAP.find(arr[i]) == MAP.end())
            MAP[arr[i]].fir = i;

        MAP[arr[i]].last = i;
    }

    int difference, differenceIndex = INT_MIN;

    unordered_map<int, IndexValue>::iterator itr;
    for (itr=MAP.begin(); itr != MAP.end(); itr++)
    {
        difference = (itr->second).last - (itr->second).fir;
        if (differenceIndex < difference)
            differenceIndex = difference;
    }
    return differenceIndex;
}
int main()
{
    int arr[] = {2, 3, 5, 1, 4, 6, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference b/w the first and last index of a number= "<<maxDifference(arr, n);
    return 0;
}
Maximum difference b/w the first and last index of a number= 6

Код Java для поиска максимальной разницы между первым и последним индексами элемента в массиве

import java.util.HashMap;
import java.util.Map;

class IndexValue
{
    int first;
    int second;
    public IndexValue()
    {
        super();
    }
}
class DifferenceOfIndexes
{
    private static int getIndexesDifferent(int[] arr)
    {
        int n = arr.length;
        int differenceIndex = 0;
        Map<Integer, IndexValue> MAP = new HashMap<Integer, IndexValue>();

        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]))
            {
                IndexValue iv = MAP.get(arr[i]);
                iv.second = i;
            }
            else
            {
                IndexValue iv = new IndexValue();
                iv.first = i;
                MAP.put(arr[i], iv);
            }
        }
        for (Map.Entry<Integer, IndexValue> entry : MAP.entrySet())
        {
            IndexValue iv = entry.getValue();
            if ((iv.second - iv.first) > differenceIndex)
            {
                differenceIndex = iv.second - iv.first;
            }
        }
        return differenceIndex;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,5,1,4,6,2,5};
        System.out.println("Maximum difference b/w the first and last index of a number= "+ getIndexesDifferent(arr));
    }
}
Maximum difference b/w the first and last index of a number= 6

Анализ сложности

Сложность времени

О (п) в котором «П» это количество элементов в массиве

Космическая сложность

О (п) в котором «П» это количество элементов в массиве