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


Ниво тешкоће Средњи
Често питани у Аццолите амазонка Пешачење МакеМиТрип Ола Цабс САП Лабс
Ред Хасх

Претпоставимо да имате поредак 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. Изаберите сваки елемент низа и узмите његов први и последњи елемент и сместите га у ХасхТабле.
  3. Пређите преко Мапа:
    1. Откријте разлику између првог и последњег индекса сваког елемента.
    2. Спремите максималну разлику у неку променљиву и наставите да је ажурирате кад год пронађете максималну вредност од претходне вредности.
  4. Врати максималну разлику.

Објашњење

Добили смо цео број низа, морамо открити разлику између првог индекса и последњег индекса сваке вредности низа. Откријте максималну разлику за било који број између његовог првог и последњег индекса. За ово ћемо користити Хасхинг. Узећемо елемент низа и сазнаћемо његов први индекс и последњи индекс или када се јавља први и последњи.

Пређите мапу након стављања свих елемената и њиховог првог и последњег индекса на мапу. Сада одаберите сваки елемент, а затим узмите њихов први и последњи индекс и откриће разлику која би требало да буде максимална од свих. Можемо користити променљиву макимумДифференце да пази на максималну разлику. Користићемо класу и њен објекат за чување првог и последњег индекса сваког елемента.

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

Пример

Арр [] = {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 као максималну разлику и то би био наш одговор.

Ц ++ код за проналажење максималне разлике између првог и последњег индекса елемента у низу

#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

Јава код за проналажење максималне разлике између првог и последњег индекса елемента у низу

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

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

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

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

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

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