Массив дахь элементийн эхний ба эцсийн индексүүдийн хоорондох хамгийн их ялгаа  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accolite Амазоны явган аялал MakeMyTrip Ola Cabs SAP лабораторууд
Array Хаш

Танд нэг массив 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: 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” массив дахь элементүүдийн тоо юм