අරාවෙහි ඇති මූලද්‍රව්‍යයක පළමු හා අවසාන දර්ශක අතර උපරිම වෙනස


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇසොලයිට් ඇමේසන් ඉහළ දැමීම 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. උපරිම වෙනස ආපසු එවන්න.

පැහැදිලි කිරීම

අපට ලබා දී ඇත්තේ අ නිඛිල අරාව, අරාවක එක් එක් අගයේ පළමු දර්ශකය සහ අවසාන දර්ශකය අතර වෙනස අප විසින් සොයාගත යුතුය. ඕනෑම අංකයක පළමු හා අවසාන දර්ශකය අතර උපරිම වෙනස සොයා ගන්න. මේ සඳහා අපි භාවිතා කිරීමට යන්නේ හැෂිං. අපි අරාව මූලද්‍රව්‍යයක් ගෙන එහි පළමු දර්ශකය සහ අවසාන දර්ශකය හෝ එය පළමු හා අවසාන වශයෙන් සිදු වූ විට සොයා ගනිමු.

සියලුම අංග සහ ඒවායේ පළමු සහ අවසාන දර්ශකය සිතියමට ඇතුළත් කිරීමෙන් පසු සිතියම හරහා ගමන් කරන්න. දැන් සෑම මූලද්‍රව්‍යයක්ම තෝරාගෙන ඒවායේ පළමු හා අවසාන දර්ශකය ගෙන එය උපරිම වශයෙන් විය යුතු වෙනස සොයා ගනී. අපට විචල්යයක් භාවිතා කළ හැකිය උපරිම වෙනස උපරිම වෙනස ගැන විමසිල්ලෙන් සිටීමට. සෑම මූලද්‍රව්‍යයකම පළමු හා අවසාන දර්ශකය ගබඩා කිරීම සඳහා අපි පන්තියක් සහ එහි වස්තුව භාවිතා කරමු.

අපි උදාහරණයක් සලකා බලමු:

උදාහරණයක්

අර [] = {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

අරාවෙහි ඇති මූලද්‍රව්‍යයක පළමු හා අවසාන දර්ශක අතර උපරිම වෙනස සොයා ගැනීමට ජාවා කේතය

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” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ