ភាពខុសគ្នាអតិបរមារវាងសន្ទស្សន៍ទីមួយនិងចុងក្រោយនៃធាតុមួយនៅក្នុងអារេ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ គួរឱ្យគោរព ក្រុមហ៊ុន Amazon ការដំឡើង MakeMyTrip អូឡាកាប មន្ទីរពិសោធន៍អេសអេស
អារេ ហាស់

ឧបមាថាអ្នកមាន អារេ of ចំនួនគត់។ បញ្ហា“ ភាពខុសគ្នាអតិបរមារវាងលិបិក្រមដំបូងនិងចុងក្រោយនៃធាតុនៅក្នុងអារេ” ស្នើឱ្យស្វែងយល់ពីភាពខុសគ្នារវាងលិបិក្រមទីមួយនិងចុងក្រោយនៃលេខនីមួយៗដែលមាននៅក្នុងអារេដូចជាភាពខុសគ្នាខ្ពស់បំផុត។

ឧទាហរណ៍

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

ការពន្យល់

សន្ទស្សន៍ទីមួយ ២ first ០

សន្ទស្សន៍ចុងក្រោយ ២ → ៦

ភាពខុសគ្នាអតិបរមា (៦-០) = ៦

ភាពខុសគ្នាអតិបរមារវាងសន្ទស្សន៍ទីមួយនិងចុងក្រោយនៃធាតុមួយនៅក្នុងអារេ

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

ការពន្យល់

សន្ទស្សន៍ទីមួយ ២ first ០

សន្ទស្សន៍ចុងក្រោយ ២ → ៦

ភាពខុសគ្នាអតិបរមា (៦-០) = ៦

ក្បួនដោះស្រាយ

  1. ឆ្លងកាត់ទាំងមូល អារេ.
  2. ជ្រើសរើសធាតុនីមួយៗនៃអារេហើយយកធាតុទីមួយនិងចុងក្រោយរបស់វាហើយផ្ទុកវាទៅក្នុង HashTable ។
  3. ឆ្លងកាត់ ផែនទី:
    1. ស្វែងយល់ពីភាពខុសគ្នារវាងសន្ទស្សន៍ទីមួយនិងសន្ទស្សន៍ចុងក្រោយនៃធាតុនីមួយៗ។
    2. រក្សាភាពខុសគ្នាអតិបរមាទៅនឹងអថេរមួយចំនួនហើយបន្តធ្វើបច្ចុប្បន្នភាពវានៅពេលណាដែលអ្នករកឃើញតម្លៃអតិបរមាខ្ពស់ជាងតម្លៃមុន។
  4. ត្រឡប់ភាពខុសគ្នាអតិបរមា។

ការពន្យល់

យើងត្រូវបានផ្តល់ឱ្យ integer អារេយើងត្រូវស្វែងយល់ពីភាពខុសគ្នារវាងសន្ទស្សន៍ទីមួយនិងសន្ទស្សន៍ចុងក្រោយនៃតំលៃនីមួយៗនៃអារេមួយ។ ស្វែងយល់ពីភាពខុសគ្នាអតិបរមាសម្រាប់លេខណាមួយរវាងសន្ទស្សន៍ទីមួយនិងចុងក្រោយ។ សម្រាប់បញ្ហានេះយើងនឹងប្រើ ហាសហាស។។ យើងនឹងយកធាតុអារេហើយនឹងរកឃើញសន្ទស្សន៍ដំបូងនិងសន្ទស្សន៍ចុងក្រោយរបស់វាឬនៅពេលវាកើតឡើងដំបូងនិងចុងក្រោយ។

បញ្ច្រាសផែនទីបន្ទាប់ពីដាក់ធាតុទាំងអស់និងសន្ទស្សន៍ដំបូងនិងចុងក្រោយរបស់វាទៅក្នុងផែនទី។ ឥឡូវជ្រើសរើសធាតុនីមួយៗហើយបន្ទាប់មកយកសន្ទស្សន៍ដំបូងនិងចុងក្រោយរបស់ពួកគេហើយនឹងរកឃើញភាពខុសគ្នាដូចជាវាគួរតែខ្ពស់បំផុត។ យើងអាចប្រើអថេរ អតិបរមាDifference រក្សាភ្នែកលើភាពខុសគ្នាអតិបរមា។ យើងនឹងប្រើថ្នាក់និងវត្ថុរបស់វាដើម្បីទុកសន្ទស្សន៍ទីមួយនិងចុងក្រោយនៃធាតុទាំងអស់។

ចូរយើងពិចារណាឧទាហរណ៍មួយ៖

ឧទាហរណ៍

មកដល់ [] = {២, ៣, ៥, ១, ៤, ៦, ២, ៥}

យើងមានការបញ្ចូលអារេ។ ដើម្បីដោះស្រាយបញ្ហានេះយើងនឹងប្រើថ្នាក់មួយ។ យើងនឹងស្វែងរកគ្រប់ធាតុទាំងអស់ប្រសិនបើវាត្រូវបានឆ្លងកាត់ជាលើកដំបូង។ បន្ទាប់មកយើងនឹងរក្សាទុកលិបិក្រមរបស់វាជាសន្ទស្សន៍ដំបូងហើយនៅពេលធាតុដដែលនោះកើតឡើងម្តងទៀត។ បន្ទាប់មករាល់ពេលយើងនឹងរក្សាទុកសន្ទស្សន៍របស់វាជាសន្ទស្សន៍ទីពីរ។ ដោយប្រើវិធីសាស្ត្រនេះយើងមានផែនទីដូចជា៖

ផែនទី៖ ១-> ៣៖ គ្មាន

២-> ០: ៦,

៣-> ១,

៤-> ៤៖ គ្មាន

២-> ០: ៦,

៦-> ៥៖ មោឃៈ

យើងនឹងឆ្លងកាត់ផែនទីហើយយើងនឹងយកតម្លៃនីមួយៗនិងពិនិត្យមើលភាពខុសគ្នានៃសូចនាកររបស់ពួកគេ។ យើងនឹងធ្វេសប្រហែសចំពោះតម្លៃទាំងអស់ដែលមានតំលៃ។ ដូច្នេះយើងមាន ២ និង ៥ ហើយចេញពីនោះ 2 មានភាពខុសគ្នាអតិបរមា (៦) រវាងសន្ទស្សន៍ទីមួយនិងចុងក្រោយ 5 ដែលមានភាពខុសគ្នា (៥) ។ ដូច្នេះយើងនឹងត្រឡប់លេខ ៦ ជាភាពខុសគ្នាអតិបរមាហើយនោះជាចម្លើយរបស់យើង។

កូដ 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 ' គឺជាចំនួនធាតុក្នុងអារេ