מאַקסימום חילוק צווישן ערשטער און לעצט ינדעקסיז פון אַן עלעמענט אין מענגע  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַקקאָליטע אַמאַזאָן שפּאַציר MakeMyTrip אָלאַ קאַבס 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. קלייַבן יעדער עלעמענט פון אַ מענגע און באַקומען זיין ערשטער און לעצט עלעמענט און סטאָרד עס אין די האַשטאַבלע.
  3. דורך די מאַפּע:
    1. געפֿינען די חילוק צווישן דער ערשטער און די לעצטע אינדעקס פון יעדער עלעמענט.
    2. סטאָר די מאַקסימום חילוק אין עטלעכע בייַטעוודיק און האַלטן עס אַפּדייטינג ווען איר געפֿינען די מאַקסימום ווערט ווי די פריערדיקע ווערט.
  4. ווייַזן מאַקסימום חילוק.

דערקלערונג

מיר זענען געגעבן אַן ינטעגער מענגע, מיר דאַרפֿן צו געפֿינען די חילוק צווישן דער ערשטער אינדעקס און די לעצטע אינדעקס פון יעדער ווערט פון אַ מענגע. געפֿינען די מאַקסימום חילוק פֿאַר יעדער נומער צווישן די ערשטע און לעצטע אינדעקס. פֿאַר דעם, מיר וועלן נוצן האַשינג. מיר וועלן נעמען אַ מענגע עלעמענט און דערוויסן זיך דער ערשטער אינדעקס און לעצטע אינדעקס אָדער ווען עס אַקערז ערשטער און לעצט.

זע אויך
געפֿינען אַ פּאָר מיט גרעסטע פּראָדוקט אין עריי

אַריבער די מאַפּע נאָך פּאַטינג אַלע די עלעמענטן און זייער ערשטער און לעצט אינדעקס אין די מאַפּע. איצט קלייַבן יעדער עלעמענט און נעמען זייער ערשטער און לעצט אינדעקס און וועט געפֿינען די חילוק אַזוי אַז עס זאָל זיין מאַקסימום פון אַלע. מיר קענען נוצן אַ בייַטעוודיק מאַקסימום דיפפערענסע צו האַלטן אַן אויג אויף די מאַקסימום חילוק. מיר וועלן נוצן אַ קלאַס און זיין כייפעץ צו קראָם דער ערשטער און די לעצטע אינדעקס פון יעדער עלעמענט.

לאָמיר באַטראַכטן אַ ביישפּיל:

בייַשפּיל

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

דזשאַוואַ קאָד צו געפֿינען די מאַקסימום חילוק צווישן די ערשטע און לעצטע ינדעקסיז פון אַן עלעמענט אין מענגע  

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

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי

אָ (N) ווו “N’ איז די נומער פון עלעמענטן אין דער מענגע

זע אויך
פּאָסטפיקס צו ינפיקס קאָנווערסיאָן

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N’ איז די נומער פון עלעמענטן אין דער מענגע