Максимално растојание помеѓу две појави на ист елемент во низата


Ниво на тешкотија Медиум
Често прашувано во Деливерија Факти Фанатици Фуркити
Низа Хаш

Да претпоставиме дека ти е даден низа со некои повторени броеви. Треба да го најдеме максималното растојание помеѓу двете исти појави на број со различен индекс, присутно во низа.

пример

влез:

низа = [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. Додека i е помала од должината на низата (n).
    1. Проверете го секој елемент од низата дали го има своето прво појавување или не на картата, ако е прво,
      1. Потоа ставете го елементот и неговиот индекс во мапа.
    2. Друго (ако веќе постои)
      1. Откријте го максималното растојание помеѓу претходниот и овој (растојание помеѓу индексот).
      2. Чувајте го максималното растојание до „МаксДистанца“.
  4. Врати се „МаксДистанца“.

Објаснување

Дадовме низа со неколку повторени елементи во неа. Нашата задача е да ја откриеме максималната разлика помеѓу позицијата на истите појави на број. Thisе користиме мапа за ова. На таа мапа, ќе ги ставиме елементите на низата како клуч и нивниот индекс како вредност. Тогаш ќе најдеме максимална разлика или растојание помеѓу двата индекси со ист број ако постои, иако треба да го најдеме растојанието помеѓу истите елементи.

На картата, секој клуч има одредена вредност како елемент на низата и нивни индекси, ако за секој елемент се најдат два индекси, тогаш ќе најдеме разлика помеѓу тие индекси и ќе најдеме поголема разлика помеѓу претходниот „МаксДистанца“ и сегашниот. И тогаш по повторување на целата низа имаме најголемо максимално растојание.

Да разгледаме пример:

пример

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 е складиран во максДистанца.

И ние го враќаме 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

Јава програма за максимално растојание помеѓу две појави на ист елемент во низата

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

Анализа на сложеност за максимално растојание помеѓу две појави на ист елемент во низата

Временска комплексност

Тој) каде „Н“ е бројот на елементи во низата.

Комплексноста на просторот

Тој) каде „Н“ е бројот на елементи во низата.