Массивдеги элементтин биринчи жана акыркы индекстеринин максималдуу айырмасы


Кыйынчылык деңгээли орто
Көп суралган Accolite Amazon селсаяктоо MakeMyTrip Ola Cabs SAP Labs
согуштук тизме таштанды

Сизде ан бар согуштук тизме 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

Algorithm

  1. Толугу менен өтүңүз согуштук тизме.
  2. Массивдин ар бир элементин тандап, анын биринчи жана акыркы элементин алып, HashTableга сактаңыз.
  3. Өтүү карта:
    1. Ар бир элементтин биринчи жана акыркы индексинин айырмасын табыңыз.
    2. Максималдуу айырманы кандайдыр бир өзгөрмөгө сактап, мурунку мааниге караганда максималдуу маанини тапкан сайын жаңыртып туруңуз.
  4. Максималдуу айырманы кайтаруу.

түшүндүрүү

Бизге ан бүтүн массив, массивдин ар бир маанисинин биринчи индекси менен акыркы индексинин айырмасын табышыбыз керек. Анын биринчи жана акыркы индексинин ортосундагы каалаган сан үчүн максималдуу айырманы билип алыңыз. Бул үчүн, биз колдоно турган болду Hashing. Биз массивдин элементин алып, анын биринчи индексин жана акыркы индексин же качан биринчи жана акыркы болгонун аныктайбыз.

Бардык элементтерди жана алардын биринчи жана акыркы индексин картага киргизгенден кийин, картаны айланып өтүңүз. Эми ар бир элементти тандап, андан кийин алардын биринчи жана акыркы индексин алып, айырмачылыкты аныктайсыз, анткени ал баарынан көп болушу керек. Биз өзгөрмө колдоно алабыз maximumDifference максималдуу айырмачылыкты байкап туруу. Биз ар бир элементтин биринчи жана акыркы индексин сактоо үчүн классты жана анын объектисин колдонобуз.

Келгиле, бир мисал карап көрөлү:

мисал

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

Бизде массив киргизилген. Муну чечүү үчүн биз классты колдонобуз. Эгерде ал биринчи жолу өтүп жаткан болсо, анда биз ар бир элементти издейбиз. Андан кийин биз анын индексин биринчи индекс катары сактайбыз жана ошол эле элемент кайрадан келгенде. Ошондо ар бир жолу биз анын индексин экинчи индекс катары сактайбыз. Бул ыкманы колдонуп, бизде төмөнкүдөй карта бар:

Карта: 1-> 3: null,

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

Комплекстик анализ

Убакыт татаалдыгы

O (N) кайда “N ' массивдеги элементтердин саны

Космостун татаалдыгы

O (N) кайда “N ' массивдеги элементтердин саны