অ্যারেতে একই উপাদান দুটি ঘটনার মধ্যে সর্বাধিক দূরত্ব


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় Delhivery ফ্যাক্সেট ধর্মান্ধদের ফোরকিটস
বিন্যাস কাটা

মনে করুন আপনি একটি দেওয়া হয় বিন্যাস কিছু পুনরাবৃত্তি সংখ্যা সঙ্গে। অ্যারেতে উপস্থিত বিভিন্ন সূচক সহ একটি সংখ্যার দুটি একই সংঘর্ষের মধ্যে সর্বাধিক দূরত্ব আমাদের খুঁজে পেতে হবে।

উদাহরণ

ইনপুট:

অ্যারে = [1, 2, 3, 6, 2, 7]

আউটপুট:

3

ব্যাখ্যা:

কারণ অ্যারে [1] এবং অ্যারে [4] এ থাকা উপাদানগুলিতে একই উপাদান রয়েছে যা সর্বোচ্চ 2 এর দূরত্ব সহ '3' হয়।

ইনপুট:

অ্যারে = [3, 4, 6, 7, 4, 8, 9, 3]

আউটপুট:

7

ব্যাখ্যা:

কারণ উপাদান অ্যারে [0] এবং অ্যারে [7] এর একই উপাদান রয়েছে যা সর্বোচ্চ 3 এর দূরত্ব সহ '3' হয়।

একই উপাদানটির দুটি ইভেন্টের মধ্যে সর্বাধিক দূরত্বের জন্য অ্যালগরিদম

  1. ঘোষণা করুন ক মানচিত্র.
  2. সেট "সর্বোচ্চ দূরত্ব" 0 তে
  3. যদিও আমি অ্যারের দৈর্ঘ্যের চেয়ে কম (n)।
    1. প্রতিটি অ্যারের উপাদান যদি এটির প্রথম উপস্থিতি থাকে বা মানচিত্রে না থাকে তা পরীক্ষা করুন, যদি প্রথমে,
      1. তারপরে একটি মানচিত্রে উপাদান এবং এর সূচি রাখুন।
    2. অন্যথায় (এটি ইতিমধ্যে বিদ্যমান থাকলে)
      1. পূর্ববর্তীটি এবং এই একের মধ্যে সর্বাধিক দূরত্ব (সূচকের মধ্যে দূরত্ব) সন্ধান করুন।
      2. সর্বোচ্চ দূরত্ব সংরক্ষণ করুন "সর্বোচ্চ দূরত্ব".
  4. প্রত্যাবর্তন "সর্বোচ্চ দূরত্ব".

ব্যাখ্যা

আমরা এতে কিছু পুনরাবৃত্তি উপাদান সহ একটি অ্যারে দিয়েছি। আমাদের কাজটি হ'ল কোনও সংখ্যার একই উপস্থিতির অবস্থানের মধ্যে সর্বাধিক পার্থক্য খুঁজে বের করা। আমরা এটির জন্য একটি মানচিত্র ব্যবহার করতে যাচ্ছি। সেই মানচিত্রে আমরা অ্যারের উপাদানগুলিকে একটি কী হিসাবে এবং তাদের সূচককে মান হিসাবে রাখতে যাচ্ছি। তারপরে আমরা একই সংখ্যার দুটি সূচকের মধ্যে বিদ্যমান পার্থক্য বা দূরত্ব সন্ধান করতে যা এটি বিদ্যমান থাকলেও একই উপাদানগুলির মধ্যে আমাদের দূরত্ব খুঁজে বের করতে হবে।

একটি মানচিত্রে, প্রতিটি কী এর অ্যারের উপাদান এবং তাদের সূচক হিসাবে এর কিছু মূল্য রয়েছে, যদি প্রতিটি উপাদানগুলির জন্য দুটি সূচক পাওয়া যায়, তবে আমরা সেই সূচকের মধ্যে পার্থক্যটি সন্ধান করতে যাচ্ছি এবং পূর্ববর্তীটির মধ্যে আরও বড় পার্থক্যটি আবিষ্কার করব "সর্বোচ্চ দূরত্ব" এবং বর্তমান এক। এবং তারপরে পুরো অ্যারেতে পুনরাবৃত্তি হওয়ার পরে আমাদের মধ্যে সর্বাধিক সর্বাধিক দূরত্ব।

আসুন একটি উদাহরণ বিবেচনা করুন:

উদাহরণ

আরআর [] = {8, 1, 3, 2, 4, 1, 3, 6, 7, 3, 1};

i = 0, এআর [i] = 8 => মাইম্যাপ = {8: 0}

i = 1, আরআর [i] = 1 => মাইম্যাপ = {8: 0, 1: 1}

i = 2, এআর [i] = 3 => মাইম্যাপ = {8: 0, 1: 1, 3: 2}

i = 3, এআর [i] = 2 => মাইম্যাপ = {8: 0, 1: 1, 3: 2, 2: 3}

i = 4, এআর [i] = 4 => মাইম্যাপ = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}

i = 5, আর [i] = 1 => মাইম্যাপ = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}, এখানে এটি বর্তমান সূচী এবং পূর্ববর্তী সূচকের মধ্যে পার্থক্য খুঁজে পাবেন '1', (5-1 = 4), 4 হ'ল সর্বাধিক দূরত্বে।

i = 6, এআর [i] = 3 => মাইম্যাপ = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4} এখানে এটি বর্তমান সূচক এবং পূর্ববর্তী সূচকের মধ্যে পার্থক্য খুঁজে পাবে ' 3 ', (6-2 = 4), তবে 4 ইতিমধ্যে সর্বোচ্চ দূরত্বে রয়েছে, সুতরাং এটি কোনও ব্যাপার নয়।

i = 7, এআর [i] = 6 => মাইম্যাপ = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7}

i = 8, আর [i] = 7 => মাইম্যাপ = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8}

i = 9, এআর [i] = 3 => মাইম্যাপ = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} এখানে এটির মধ্যে পার্থক্যটি পাওয়া যাবে '3' এর বর্তমান সূচক এবং পূর্ববর্তী সূচক, (9-3 = 6), 6 সর্বাধিক দূরত্বে সঞ্চয়।

i = 10, এআর [i] = 3 => মাইম্যাপ = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} এখানে এটির মধ্যে পার্থক্যটি পাওয়া যাবে '1' এর বর্তমান সূচক এবং পূর্ববর্তী সূচক, (10-1 = 9), 9 সর্বাধিক দূরত্বে সঞ্চয়।

এবং আমরা 9 ​​হিসাবে সর্বাধিক দূরত্বে ফিরে আসি।

বাস্তবায়ন

অ্যারেতে একই উপাদানটির দুটি ইভেন্টের মধ্যে সর্বাধিক দূরত্বের জন্য সি ++ প্রোগ্রাম

#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

অ্যারেতে একই উপাদানটির দুটি ইভেন্টের মধ্যে সর্বোচ্চ দূরত্বের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।