배열에서 동일한 요소의 두 발생 사이의 최대 거리-

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러

당신이 주어진다고 가정하십시오 정렬 반복되는 숫자로. 배열에 존재하는 서로 다른 인덱스를 가진 숫자의 동일한 두 발생 사이의 최대 거리를 찾아야합니다.

차례

예

입력:

배열 = [1, 2, 3, 6, 2, 7]

출력:

설명 :

배열 [1] 및 배열 [4]의 요소는 최대 거리가 2 인 '3'인 동일한 요소를 갖기 때문입니다.

입력:

배열 = [3, 4, 6, 7, 4, 8, 9, 3]

출력:

설명 :

요소 배열 [0] 및 배열 [7]에는 최대 거리가 3 인 '3'인 동일한 요소가 있기 때문입니다.

동일한 요소의 두 발생 사이의 최대 거리에 대한 알고리즘

선언 지도.
세트 "maxDistance" 0합니다.
i는 배열의 길이 (n)보다 작습니다.
1. 각 배열 요소가 처음 발생한 경우 맵에 없는지 확인하십시오.
  1. 그런 다음 요소와 색인을지도에 넣습니다.
2. Else (이미 존재하는 경우)
  1. 이전 거리와이 거리 (색인 사이의 거리) 사이의 최대 거리를 찾으십시오.
  2. 최대 거리 저장 "maxDistance".
반품 "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;
}

배열에서 동일한 요소의 두 발생 사이의 최대 거리를위한 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));
    }
}

배열에서 동일한 요소의 두 발생 간 최대 거리에 대한 복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러