Фарқи максималии байни нишондиҳандаҳои аввал ва охирини элемент дар массив


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Accolite Amazon саёҳат кардан MakeMyTrip Ola Cabs Лабораторияҳои SAP
тартиботи ҳарбӣ Хаш

Фарз мекунем, ки шумо як асал 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. Фарқи ҳадди аксарро баргардонед.

Шарҳ

Ба мо як ҳамаҷониба массиви, мо бояд фарқи байни индекси аввал ва индекси охирини ҳар як арзиши массивро ёбем. Фарқи максималии ҳар рақамро байни индекси аввал ва охирини он ёбед. Барои ин, мо истифода бурданием Хашм. Мо унсури массивро мегирем ва нишондиҳандаи аввал ва индекси охирини онро ё вақте ки он аввал ва охирин рух медиҳад, пайдо мекунем.

Пас аз гузоштани ҳамаи элементҳо ва индекси аввал ва охирини онҳо ба харита, гардиш кунед. Акнун ҳар як унсурро интихоб кунед ва пас индекси аввал ва охирини онҳоро гиред ва фарқиятро фаҳмед, ки он бояд ҳадди аксар бошад. Мо метавонем тағирёбандаро истифода барем Фарқияти ҳадди аксар то фарқи ҳадди аксарро мушоҳида кунем. Мо синф ва объекти онро барои нигоҳ доштани индекси аввал ва охирини ҳар як элемент истифода хоҳем кард.

Биёед як мисолро дида бароем:

мисол

Арр [] = {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

Таҳлили мураккабӣ

Мураккабии вақт

Эй (н) ки дар “Н” шумораи унсурҳои массив аст

Мураккабии фазо

Эй (н) ки дар “Н” шумораи унсурҳои массив аст