أقصى فرق بين الفهارس الأولى والأخيرة لعنصر في المصفوفة  


مستوى الصعوبة متوسط
كثيرا ما يطلب في Accolite أمازون رفع ميك ماي تريب علا سيارة أجرة مختبرات 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

تحليل التعقيد  

تعقيد الوقت

O (ن) أين "ن' هو عدد العناصر في المصفوفة

انظر أيضا
Postfix لتحويل Infix

تعقيد الفضاء

O (ن) أين "ن' هو عدد العناصر في المصفوفة