두 요소 간의 최소 차이 찾기

난이도 쉽게
자주 묻는 질문 아마존
배열 정렬조회수 53

문제 정책

당신은 주어진 정렬 정수 문제 설명은 배열에 주어진 두 요소 간의 최소 차이를 찾을 것을 요청합니다.

arr[] = {11,1,6,8,20,13}
2

설명 : 11과 13 사이의 최소 차이는 2입니다.

arr[] = {19,14,80,200,32,29}
3

설명 : 32과 29 사이의 최소 차이는 3입니다.

 

두 요소 간의 최소 차이를 찾는 알고리즘

1. Sort the array.
2. Set the output to the maximum value of an integer.
3. Check the minimum difference of adjacent pairs and get the minimum difference into the output.
4. Return output.

설명 E

정수 배열을 제공했습니다. 두 요소 사이의 최소 차이를 찾아야합니다. 이를 위해 먼저 배열을 정렬하고 오름차순으로 배열을 정렬해야합니다. 이것은 우리가 횡단 할 것이고 우리는 그들과 각각의 쌍과 그 차이를 확인할 것이기 때문입니다. 정렬 O (n log n) 시간이 걸리므로 효율적인 것으로 간주 할 수 있습니다.

예를 들어 보겠습니다.

Arr [] = {11,1,6,8,20,13}, 정렬하겠습니다. 배열을 정렬 한 후 배열은 {1, 6, 8, 11, 13, 20}입니다. 출력값을 정수가 가질 수있는 최대 값으로 설정하겠습니다. 이것은 우리가 최소값을 찾을 것이고이를 위해 최소 요소와 비교해야하기 때문입니다. 그리고 우리가 더 큰 숫자가 없다면 우리는 비교할 수없고 또한 찾을 수 없을 것입니다. 우리가 선택한 초기 최소값이 답이 될 것이기 때문입니다. 그 가치는 우리가 계산하는 동안 발생하거나 발생하지 않을 수 있습니다.

이제 우리는 이제 인접한 각 쌍의 차이를 얻을 것입니다. 처음부터 우리가 1과 6을 취하면 최소 차이로 5가 있고, 6과 8 사이에는 최소 차이로 2가 있고, 8과 11에는 3이 있으므로 이미 2가있는 것으로 간주하지 않을 것입니다. 차이는 최소 3입니다. 11과 13은 최소 차이가 2이고 13과 20은 차이가 7이지만 7은 현재 최소 차이 인 2보다 더 큽니다. 따라서 2를 선택합니다. 출력으로 반환하고 반환합니다. 그래서 이것은 우리가 두 요소 사이의 최소 차이를 찾는 방법입니다.

두 요소 간의 최소 차이 찾기

두 요소 간의 최소 차이 찾기를위한 C ++ 구현

#include<bits/stdc++.h>
#include<algorithm>

using namespace std;

int getMinimumDif(int arr[], int n)
{
    sort(arr, arr+n);

    int output = INT_MAX;

    for (int i=0; i<n-1; i++)
        if (arr[i+1] - arr[i] < output)
            output = arr[i+1] - arr[i];

    return output;
}
int main()
{
    int arr[] = {11,1,6,8,20,13};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum difference: " << getMinimumDif(arr, n);
    return 0;
}
Minimum difference: 2

두 요소 간의 최소 차이 찾기를위한 Java 구현

import java.util.Arrays;

class minimumDiffPair
{
    static int getMinimumDif(int[] arr, int n)
    {
        Arrays.sort(arr);

        int output = Integer.MAX_VALUE;

        for (int i=0; i<n-1; i++)
            if (arr[i+1] - arr[i] < output)
                output = arr[i+1] - arr[i];

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {11,1,6,8,20,13};
        System.out.println("Minimum difference : "+getMinimumDif(arr, arr.length));
    }
}
Minimum difference : 2

복잡성 분석 

시간 복잡성

정렬 알고리즘을 사용하기 때문에 O (n 로그 n) 시간 복잡성, 어디에 "엔"  배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔"  배열의 요소 수입니다. 여기서 우리는 입력을 위해 배열을 사용하여 공간 복잡성을 선형으로 만듭니다.

Translate »