მაქსიმალური მანძილი მასივში იგივე ელემენტის ორ მოვლენას შორის


Რთული ტური საშუალო
ხშირად ეკითხებიან ადგილზე მიტანა ფაქტები ფანატიკა Fourkites
Array Hash

დავუშვათ, რომ მოგეცათ მასივი რამდენიმე განმეორებითი რიცხვით. ჩვენ უნდა ვიპოვნოთ მაქსიმალური მანძილი სხვადასხვა ინდექსის მქონე ციფრის ორ იგივე შემთხვევას შორის, რომელიც მასივშია.

მაგალითი

შეყვანის:

მასივი = [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" to 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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.