두 숫자 사이의 최소 거리 찾기

문제 정책

배열과 x와 y라는 두 개의 숫자를 제공했습니다. "두 숫자 사이의 최소 거리 찾기"문제는 둘 사이의 가능한 최소 거리를 알아 내도록 요구합니다. 주어진 배열은 공통 요소를 가질 수 있습니다. x와 y가 모두 다르다고 가정 할 수 있습니다.

예

arr[] = {1, 3, 2, 5, 8, 2, 5, 1}

x = 2

y=8

1

설명 : 2의 인덱스는 2와 5이고 8의 인덱스는 4이므로 주어진 두 숫자 사이의 최소 거리를 계산하는 인덱스를 사용합니다.

arr[] = {1, 3, 2, 5, 8, 2, 5, 1}

x = 3

y=5

2

설명 : 인덱스 3은 1이고 인덱스 5는 3이므로 둘 사이의 최소 거리는 3-1 = 2입니다.

arr[] = {2, 4, 6, 8, 2, 5, 0, 56}

x = 6

y=5

3

설명 : 6의 색인은 2이고 색인 5는 5이므로 둘 사이의 최소 거리는 5-2 = 3입니다.

두 숫자 사이의 최소 거리를 찾는 알고리즘

1. Set flag to -1 and output to the Maximum value of an Integer.
2. Traverse the array from i = 0 to i < n.
    1. Check if the array element is either equal to x or equal to y.
    2. Check if flag is not equal to i and arr[i] is not equal to arr[flag].
        1. If the condition is true, then find out the minimum between the output and i - flag.
3. Return output.

설명

우리는 정렬 정수와 x와 y라고하는 두 개의 정수입니다. 주어진 두 숫자 x와 y 사이의 최소 거리를 찾아야합니다. 최소 거리를 알아보기 위해 두 개의 숫자 쌍을 확인합니다. 우리가받은 번호는 순회 중에 만 확인합니다. 배열 현재 요소와 일치하는 두 숫자 중 하나를 검색합니다. 사실이 확인되면 반복 요소가 아닌지 또는 동일한 요소인지 확인합니다. 모든 조건이 참이면 출력 값만 업데이트합니다.

현재 배열 요소가 x 또는 y와 같고 인덱스 및 동일한 요소의 다른 조건이 거짓이되었습니다. 그런 다음 플래그를 업데이트하고 현재 요소 인덱스를 플래그에 저장합니다. 예를 들어 보겠습니다.

예

도착 [] = {1, 3, 2, 5, 8, 2, 5, 1}, x = 2, y = 8

출력 = 정수의 최대 값, 플래그 = – 1

우리는 x = 2와 y = 8의 두 숫자를주었습니다

• i = 0, arr [i]가 2인지 또는 arr [i]가 8인지 확인하지만 조건이 충족되지 않습니다.

조건은 i = 2 일 때 만족합니다.

• i = 2, arr [i]는 2와 같습니다.

플래그를 확인하고 플래그가 여전히 -1이기 때문에 거짓입니다. 따라서 플래그를 플래그 = 2로 업데이트하면 입력되지 않습니다.

• 다음으로, i = 4, arr [i] = 8 일 때, flag는 -1과 같지 않고 arr [i]는 arr [flag]와 같지 않습니다. 우리는 같은 숫자를 다시 찾지 않고 거리를 얻지 못하도록이 조건을 확인하고 있습니다.

이제 출력을 = 4 – 2 = 2로 업데이트합니다. 또한 플래그를 업데이트합니다 = 4

• 다시 i = 5, arr [i] = 2에서 조건이 참이고 flag가 -1과 같지 않고 arr [i]가 arr [flag]와 같지 않으므로 출력을 다시 다음과 같이 업데이트합니다. min (4, 5-4)과 1 사이의 최소값이 출력에서 ​​업데이트됩니다.

이제 배열 요소 arr [1] = 4과 arr [8] = 5 사이의 최소 거리가 2입니다.

출력 = 1.

핀

암호

두 숫자 사이의 최소 거리를 찾는 C ++ 코드

#include<bits/stdc++.h>

using namespace std;

int getMinimumDistance(int arr[], int n, int x, int y)
{
    int flag=-1;
    int output=INT_MAX;

    for(int i = 0 ; i < n ; i++)
    {
        if(arr[i] ==x || arr[i] == y)
        {
            if(flag != -1 && arr[i] != arr[flag])
            {
                output = min(output,i-flag);
            }

            flag=i;
        }
    }
    if(output==INT_MAX)
        return -1;

    return output;
}

int main()
{
    int arr[] = {1, 3, 2, 5, 8, 2, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2;
    int y = 8;

    cout << "Minimum possible distance between " << x <<" and " << y << " : "<<getMinimumDistance(arr, n, x, y);
    return 0;
}

Minimum possible distance between 2 and 8 : 1

두 숫자 사이의 최소 거리를 찾는 Java 코드

class MinimumDistanceBwNumbers
{
    public static int getMinimumDistance(int arr[], int n, int x, int y)
    {
        int flag=-1;
        int output=Integer.MAX_VALUE;

        for(int i = 0 ; i < n ; i++)
        {
            if(arr[i] ==x || arr[i] == y)
            {
                if(flag != -1 && arr[i] != arr[flag])
                {
                    output = Math.min(output,i-flag);
                }

                flag=i;
            }
        }
        if(output==Integer.MAX_VALUE)
            return -1;

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 3, 2, 5, 8, 2, 5, 1};
        int n = arr.length;
        int x = 2;
        int y = 8;

        System.out.println("Minimum possible distance between " + x + " and " + y + ": " + getMinimumDistance(arr, n, x, y));
    }
}

Minimum possible distance between 2 and 8: 1

복잡성 분석

시간 복잡성

단일 순회는 알고리즘이 선형 시간 복잡도로 실행되도록합니다. O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

의 위에) 입력을 저장하기 위해 배열을 사용하기 때문에 공간 복잡성. 그러나 최소 거리를 찾는 알고리즘에는 O (1) 추가 공간이 필요합니다.