Знайдіть мінімальну різницю між будь-якими двома елементами


Рівень складності Легко
Часто запитують у Амазонка
масив Сортування

Постановка проблеми

Вам дано масив цілих чисел. Постановка задачі просить знайти мінімальну різницю між будь-якими двома елементами, заданими в масиві.

Приклад

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) часова складність, де "N"  - кількість елементів у масиві.

Складність простору

О (п) де "N"  - кількість елементів у масиві. Тут ми використовуємо масив для введення, роблячи його лінійним за простором складності.