ចម្ងាយអតិបរមារវាងការកើតឡើងពីរដងនៃធាតុតែមួយនៅក្នុងអារេ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ដេលីវ៉ាយ រោងចក្រ និយមជ្រុល Fourkites
អារេ ហាស់

ឧបមាថាអ្នកត្រូវបានផ្តល់ឱ្យមួយ អារេ ជាមួយលេខម្តងហើយម្តងទៀត។ យើងត្រូវរកចម្ងាយអតិបរិមារវាងការកើតឡើងដូចគ្នាពីរនៃលេខដែលមានសន្ទស្សន៍ខុសគ្នាបង្ហាញជាអារេ។

ឧទាហរណ៍

បញ្ចូល:

អារេ = [១, ២, ៣, ៦, ២, ៧]

លទ្ធផល:

3

ការពន្យល់:

ពីព្រោះធាតុនៅអារេ [១] និងអារេ [៤] មានធាតុដូចគ្នាដែលជា“ ២” ដែលមានចម្ងាយអតិបរមា ៣ ។

បញ្ចូល:

អារេ = [៣, ៤, ៦, ៧, ៤, ៨, ៩, ៣]

លទ្ធផល:

7

ការពន្យល់:

ពីព្រោះអារេធាតុ [០] និងអារេ [៧] មានធាតុដូចគ្នាដែលជា '៣' ដែលមានចម្ងាយអតិបរមា ៣ ។

ក្បួនដោះស្រាយសម្រាប់ចម្ងាយអតិបរមារវាងការកើតឡើងពីរនៃធាតុដូចគ្នា

  1. ប្រកាសក ផែនទី.
  2. កំណត់ “ ភាពធន់ខ្ពស់” ទៅ 0 ។
  3. ខណៈពេលដែលខ្ញុំតិចជាងប្រវែងអារេ (n) ។
    1. ពិនិត្យធាតុអារេនីមួយៗប្រសិនបើវាមានការកើតឡើងលើកដំបូងឬមិនមាននៅក្នុងផែនទីប្រសិនបើដំបូង
      1. បន្ទាប់មកដាក់ធាតុនិងសន្ទស្សន៍របស់វានៅក្នុងផែនទី។
    2. ផ្សេងទៀត (ប្រសិនបើវាមានរួចហើយ)
      1. ស្វែងយល់ពីចម្ងាយអតិបរមារវាងលេខមុននិងមួយនេះ (ចម្ងាយរវាងសន្ទស្សន៍) ។
      2. ទុកចម្ងាយអតិបរមាទៅ “ ភាពធន់ខ្ពស់”.
  4. ត្រឡប់ទៅវិញ “ ភាពធន់ខ្ពស់”.

ការពន្យល់

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

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

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

ឧទាហរណ៍

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

i = 0, មកដល់ [ខ្ញុំ] = ៨ => myMap = {៨: ០}

i = 1, មកដល់ [ខ្ញុំ] = 1 => myMap = {8: 0, 1: 1}

ខ្ញុំ = ២, មកដល់ [ខ្ញុំ] = ៣ => myMap = {៨: ០, ១: ១, ៣: ២}

ខ្ញុំ = ៣, មកដល់ [ខ្ញុំ] = ២ => myMap = {៨: ០, ១: ១, ៣: ២, ២: ៣}

ខ្ញុំ = ៤, មកដល់ [ខ្ញុំ] = ៤ => myMap = {៨: ០, ១: ១, ៣: ២, ២: ៣, ៤: ៤}

i = 5, មកដល់ [ខ្ញុំ] = 1 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}, នៅទីនេះវានឹងរកឃើញភាពខុសគ្នារវាងសន្ទស្សន៍បច្ចុប្បន្ននិងសន្ទស្សន៍មុនរបស់ '1', (5-1 = 4), 4 ត្រូវបានផ្ទុកនៅក្នុងអ៊ីដ្រូសែនធន់ទ្រាំ។

i = 6, មកដល់ [ខ្ញុំ] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4} នៅទីនេះវានឹងរកឃើញភាពខុសគ្នារវាងសន្ទស្សន៍បច្ចុប្បន្ននិងសន្ទស្សន៍មុនរបស់ ' 3 ', (6-2 = 4), ប៉ុន្តែ 4 មាននៅក្នុងភាពធន់ទ្រាំអតិបរមាហើយដូច្នេះវាមិនមានបញ្ហាទេ។

i = 7, មកដល់ [ខ្ញុំ] = 6 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7}

ខ្ញុំ = ៨, មកដល់ [ខ្ញុំ] = ៧ => myMap = {៨: ០, ១: ១, ៣: ២, ២: ៣, ៤: ៤, ៦: ៧, ៧: ៨}

i = 9, មកដល់ [ខ្ញុំ] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} នៅទីនេះវានឹងរកឃើញភាពខុសគ្នារវាង សន្ទស្សន៍បច្ចុប្បន្ននិងសន្ទស្សន៍មុននៃ '៣', (៩-៣ = ៦), ៦ ត្រូវបានផ្ទុកនៅក្នុងម៉ាឌ្រីដធន់ទ្រាំ។

i = 10, មកដល់ [ខ្ញុំ] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} នៅទីនេះវានឹងរកឃើញភាពខុសគ្នារវាង សន្ទស្សន៍បច្ចុប្បន្ននិងសន្ទស្សន៍មុននៃ '៣', (៩-៣ = ៦), ៦ ត្រូវបានផ្ទុកនៅក្នុងម៉ាឌ្រីដធន់ទ្រាំ។

ហើយយើងត្រឡប់ maxDistance ដូច ៩ ។

ការអនុវត្តន៍

កម្មវិធី C ++ សម្រាប់ចម្ងាយអតិបរមារវាងការកើតឡើងពីរនៃធាតុតែមួយនៅក្នុងអារេ

#include<bits/stdc++.h>
using namespace std;

int getDistance(int arr[], int n)
{
    unordered_map<int, int> my_map;
    int maxDistance = 0;
    for (int i=0; i<n; i++)
    {
        if (my_map.find(arr[i]) == my_map.end())
            my_map[arr[i]] = i;
        else
            maxDistance = max(maxDistance, i - my_map[arr[i]]);
    }

    return maxDistance;
}
int main()
{
    int arr[] = {8, 1, 3, 2, 4, 1, 3, 6, 7, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getDistance(arr, n);
    return 0;
}
9

កម្មវិធីចាវ៉ាសម្រាប់ចម្ងាយអតិបរមារវាងការកើតឡើងពីរនៃធាតុតែមួយនៅក្នុងអារេ

import java.io.*;
import java.util.*;

class distanceBSameNumbers
{
    static int getDistance(int[] arr, int n)
    {
        HashMap<Integer,Integer> my_map = new HashMap<>();

        int maxDistance = 0;

        for (int i = 0; i < n; i++)
        {
            if (!my_map.containsKey(arr[i]))
                my_map.put(arr[i], i);

            else
                maxDistance = Math.max(maxDistance, i - my_map.get(arr[i]));
        }

        return maxDistance;
    }
    public static void main(String args[])
    {
        int arr[] = {8,1,3,2,4,1,3,6,7,3,1};
        int n = arr.length;
        System.out.println(getDistance(arr, n));
    }
}
9

ការវិភាគស្មុគស្មាញសម្រាប់ចម្ងាយអតិបរមារវាងការកើតឡើងពីរនៃធាតុតែមួយនៅក្នុងអារេ

ស្មុគស្មាញពេលវេលា

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។