අරාවෙහි එකම මූලද්‍රව්‍යයේ අවස්ථා දෙකක් අතර උපරිම දුර


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ දිල්ලි ෆැක්ට්සෙට් උන්මත්තකයෝ ෆෝකයිට්
අරා හැෂ්

ඔබට ලබා දී ඇතැයි සිතමු අරාව නැවත නැවතත් සංඛ්‍යා සමඟ. අරාවෙහි පවතින විවිධ දර්ශකයක් සහිත සංඛ්‍යාවක එකම අවස්ථා දෙක අතර උපරිම දුර අප සොයා ගත යුතුය.

උදාහරණයක්

ආදානය:

array = [1, 2, 3, 6, 2, 7]

ප්රතිදාන:

3

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

අරාව [1] සහ අරාව [4] හි ඇති මූලද්‍රව්‍යවල උපරිම දුර 2 ක් සහිත '3' සමාන මූලද්‍රව්‍යයන් ඇති බැවිනි.

ආදානය:

array = [3, 4, 6, 7, 4, 8, 9, 3]

ප්රතිදාන:

7

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

මූලද්‍රව්‍ය අරාව [0] සහ අරාව [7] එකම මූලද්‍රව්‍ය '3' වන අතර උපරිම දුර 3 කි.

එකම මූලද්‍රව්‍යයේ අවස්ථා දෙකක් අතර උපරිම දුර සඳහා ඇල්ගොරිතම

  1. සිතියම.
  2. කට්ටලයක් “මැක්ස් ඩිස්ටන්ස්” 0 දක්වා.
  3. මම අරාවෙහි දිගට වඩා අඩු (n).
    1. සෑම අරා මූලද්‍රව්‍යයකම පළමු සිදුවීම හෝ සිතියමක තිබේදැයි පරීක්ෂා කරන්න, පළමුව නම්,
      1. ඉන්පසු මූලද්‍රව්‍යය සහ එහි දර්ශකය සිතියමකට දමන්න.
    2. වෙනත් (එය දැනටමත් තිබේ නම්)
      1. පෙර සහ මේ අතර ඇති උපරිම දුර සොයා ගන්න (දර්ශකය අතර දුර).
      2. වෙත උපරිම දුර ගබඩා කරන්න “මැක්ස් ඩිස්ටන්ස්”.
  4. ආපසු “මැක්ස් ඩිස්ටන්ස්”.

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

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

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

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

උදාහරණයක්

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

i = 0, arr [i] = 8 => myMap = {8: 0}

i = 1, arr [i] = 1 => myMap = {8: 0, 1: 1}

i = 2, arr [i] = 3 => myMap = {8: 0, 1: 1, 3: 2}

i = 3, arr [i] = 2 => myMap = {8: 0, 1: 1, 3: 2, 2: 3}

i = 4, arr [i] = 4 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}

i = 5, arr [i] = 1 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4}, මෙහි එය වර්තමාන දර්ශකය සහ පෙර දර්ශකය අතර වෙනස සොයා ගනී. '1', (5-1 = 4), 4 යනු උපරිම විස්තාරකයේ ගබඩා කර ඇත.

i = 6, arr [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4} මෙන්න එය වර්තමාන දර්ශකය සහ පෙර දර්ශකය අතර වෙනස සොයා ගනී. 3 ', (6-2 = 4), නමුත් 4 දැනටමත් උපරිම විස්තාරකයේ පවතින බැවින් එය වැදගත් නොවේ.

i = 7, arr [i] = 6 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7}

i = 8, arr [i] = 7 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8}

i = 9, arr [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} මෙන්න එය අතර වෙනස සොයා ගනී වර්තමාන දර්ශකය සහ පෙර දර්ශකය වන '3', (9-3 = 6), 6 උපරිම විස්තාරකයේ ගබඩා කර ඇත.

i = 10, arr [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4, 6: 7, 7: 8} මෙන්න එය අතර වෙනස සොයා ගනී වර්තමාන දර්ශකය සහ පෙර දර්ශකය වන '1', (10-1 = 9), 9 උපරිම විස්තාරකයේ ගබඩා කර ඇත.

අපි මැක්ස් ඩිස්ටන්ස් 9 ලෙස නැවත ලබා දෙන්නෙමු.

ක්රියාත්මක කිරීම

අරාවෙහි එකම මූලද්‍රව්‍යයේ අවස්ථා දෙකක් අතර උපරිම දුර සඳහා 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” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.