מרחק מקסימאלי בין שני מקרים של אותו אלמנט במערך


רמת קושי בינוני
נשאל לעתים קרובות מסירה סט עובדות קנאות פורקיטים
מערך בליל

נניח שניתן לך מערך עם מספרים חוזרים ונשנים. עלינו למצוא את המרחק המרבי בין שתי המופעים אותו מספר עם אינדקס שונה, הקיים במערך.

דוגמה

קלט:

מערך = [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. לקבוע "MaxDistance" אל 0.
  3. בעוד i קטן מאורך המערך (n).
    1. בדוק כל אלמנט מערך אם המופע הראשון שלו או לא נמצא במפה, אם הראשון,
      1. ואז שים את האלמנט ואת האינדקס שלו במפה.
    2. אחרת (אם זה כבר קיים)
      1. גלה את המרחק המרבי בין הקודם לזה (מרחק בין אינדקס).
      2. אחסן מרחק מרבי ל "MaxDistance".
  4. לחזור "MaxDistance".

הסבר

נתנו מערך עם כמה אלמנטים חוזרים ונשנים בו. המשימה שלנו היא לגלות את ההבדל המרבי בין המיקום של אותן התרחשויות של מספר. אנו נשתמש במפה לשם כך. במפה זו אנו הולכים לשים רכיבי מערך כמפתח ואת האינדקס שלהם כערך. לאחר מכן אנו נמצא את ההפרש או המרחק המרבי בין שני האינדקסים של אותו מספר אם הם קיימים, אם כי עלינו למצוא את המרחק בין אותם אלמנטים.

במפה, לכל מפתח יש ערך כלשהו כאלמנט המערך והאינדקסים שלהם, אם עבור כל אלמנט ישנם שני אינדקסים, אנו נמצא את ההבדל בין אותם אינדקסים ונמצא את ההבדל הגדול יותר בין הקודם "MaxDistance" וזה הנוכחי. ואז לאחר איטרציה לאורך כל המערך יש לנו את המרחק המרבי הגדול ביותר.

הבה נבחן דוגמה:

דוגמה

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 הוא חנות ב- maxDistance.

i = 6, arr [i] = 3 => myMap = {8: 0, 1: 1, 3: 2, 2: 3, 4: 4} כאן הוא ימצא את ההבדל בין המדד הנוכחי לאינדקס הקודם של ' 3 ', (6-2 = 4), אבל 4 כבר נמצא ב- maxDistance, אז זה לא משנה.

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 מאוחסן ב- maxDistance.

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 מאוחסן ב- maxDistance.

ואנחנו מחזירים את maxDistance כ- 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

תוכנית Java למרחק מרבי בין שני מופעים של אותו אלמנט במערך

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

ניתוח מורכבות למרחק מרבי בין שני מופעים של אותו אלמנט במערך

מורכבות זמן

O (n) איפה "N" הוא מספר האלמנטים במערך.

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך.