Екі санның арасындағы минималды арақашықтықты табыңыз


Күрделілік дәрежесі оңай
Жиі кіреді КупонDunia Coursera Дели Moonfrog зертханалары PayPal Paytm Snapchat
Array

Проблемалық мәлімдеме

Сіз 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-ге тең, ал индекстердің тағы бір шарты және сол элементтер жалған болып шықты. Содан кейін біз жалаушаны жаңартып, элементтің ағымдағы индексін жалаушаға сақтаймыз. Мысалды қарастырып, мынаны қарастырайық:

мысал

Arr [] = {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 болғанда, жалауша -1-ге тең емес, сонымен қатар arr [i] arr [жалауға] тең емес. Біз дәл осы санды қайтадан тауып, оның арақашықтығын білмес үшін осы шартты тексеріп жатырмыз.

Сонымен, біз енді шығынды = 4 - 2 = 2 етіп жаңартамыз, сонымен қатар жалаушаны = 4 жаңартамыз

  • Тағы да i = 5, arr [i] = 2 болғанда, біз шартты шынайы деп табамыз, сонымен қатар жалауша -1-ге тең емес және arr [i] arr [жалаушыға] тең емес, сондықтан шығарылымды қайтадан жаңартамыз мин (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) қайда «N» - бұл массивтегі элементтер саны.

Ғарыштың күрделілігі

O (N) кеңістіктің күрделілігі, өйткені енгізуді сақтау үшін массивті қолданамыз. Бірақ минималды қашықтықты табу алгоритмі үшін O (1) қосымша орын қажет.