მაქსიმალური განსხვავება მასივის ელემენტის პირველ და ბოლო ინდექსებს შორის


Რთული ტური საშუალო
ხშირად ეკითხებიან თანამოსაყრელი Amazon ლაშქრობა MakeMyTrip ოლა კაბინები SAP ლაბორატორიები
Array 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. დააბრუნე მაქსიმალური სხვაობა.

განმარტება

ჩვენ გვაძლევენ მთელი რიცხვი მასივი, ჩვენ უნდა გავარკვიოთ განსხვავება მასივის თითოეული მნიშვნელობის პირველ და ბოლო ინდექსს შორის. შეიტყვეთ მაქსიმალური განსხვავება ნებისმიერი რიცხვისთვის მის პირველ და ბოლო ინდექსს შორის. ამისათვის ჩვენ ვაპირებთ გამოვიყენოთ ჰაშინგი. ჩვენ ავიღებთ მასივის ელემენტს და გავარკვევთ მის პირველ ინდექსს და ბოლო ინდექსს, ან როდის ხდება ეს პირველი და ბოლო.

გაიარეთ რუკაზე ყველა ელემენტისა და მათი პირველი და ბოლო ინდექსის რუქაზე განთავსების შემდეგ. ახლა აარჩიეთ თითოეული ელემენტი, შემდეგ აიღეთ მათი პირველი და ბოლო ინდექსი და გაიგებთ იმ განსხვავებას, რომ ის მაქსიმალური უნდა იყოს ყველასათვის. შეგვიძლია გამოვიყენოთ ცვლადი მაქსიმალური სხვაობა მაქსიმალური განსხვავებისთვის თვალი რომ ადევნოს. ჩვენ ვიყენებთ კლასს და მის ობიექტს ყველა ელემენტის პირველი და ბოლო ინდექსის შესანახად.

განვიხილოთ მაგალითი:

მაგალითი

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

ჩვენ გვაქვს მასივი. ამის გადასაჭრელად გამოვიყენებთ კლასს. ჩვენ ვეძებთ ყველა ელემენტს, თუ იგი პირველად განიხილება. შემდეგ ჩვენ შევინახავთ მის ინდექსს, როგორც პირველ ინდექსს და როდესაც იგივე ელემენტი კვლავ შემოვა. ყოველ ჯერზე ჩვენ ვინახავთ მის ინდექსს, როგორც მეორე ინდექსს. ამ მეთოდის გამოყენებით ჩვენ გვაქვს რუკა, როგორც:

რუკა: 1-> 3: null,

2-> 0: 6,

3-> 1, ნული,

4-> 4: null,

5-> 2: 7,

6-> 5: ნული

ჩვენ გადავკვეთთ რუქას და ავიღებთ თითოეულ მნიშვნელობას და გადავამოწმებთ მათი ინდექსების განსხვავებებს. ჩვენ უგულებელყოფთ ყველა მნიშვნელობას, რომელსაც აქვს null მნიშვნელობა. ჩვენ გვაქვს 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

ჯავის კოდი მასივის ელემენტის პირველ და ბოლო ინდექსებს შორის მაქსიმალური განსხვავების მოსაძებნად

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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა