Фарқи ҳадди аққал байни ҳарду унсурро ёбед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon
тартиботи ҳарбӣ Sorting

Изҳороти мушкилот

Ба шумо як асал ададҳо. Дар баёнияи масъала хоҳиш карда мешавад, ки фарқи ҳадди аққал байни ҳарду унсури дар массив додашударо ёбед.

мисол

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

Мо массиви бутун додем. Мо бояд фарқи ҳадди аққали байни ҳарду унсурро пайдо кунем. Барои ин, аввал массивро ҷудо карданӣ ҳастем, мо бояд массивро бо тартиби афзоиш ҷудо кунем. Ин аз он сабаб аст, ки мо тай карданием ва ҳар як ҷуфтро бо онҳо ва тафовути онҳоро месанҷем. Sorting вақт 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-ро ҷамъ хоҳем кард ҳамчун баромади мо ва онро баргардонед. Ҳамин тавр, мо ҳамин тавр фарқияти ҳадди аққали байни ҳарду унсурро пайдо мекунем.

Фарқи ҳадди аққал байни ҳарду унсурро ёбед

Амалисозӣ дар 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 Log n) мураккабии вақт, ки дар "Н"  шумораи унсурҳои массив аст.

Мураккабии фазо

Эй (н) ки дар "Н"  шумораи унсурҳои массив аст. Дар ин ҷо, мо массивро барои вуруд истифода мебарем, ки он дар мураккабии фазо хатӣ аст.