Хоёр тооны хоорондох хамгийн бага зайг ол


Хэцүү байдлын түвшин Easy
Байнга асуудаг КупонДуниа Coursera Дели Moonfrog лабораторууд PayPal Paytm Snapchat
Array

Асуудлын мэдэгдэл

Та массив, 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-тэй тэнцүү байх ба индекс ба ижил элементүүдийн өөр нөхцөл нь худлаа болжээ. Дараа нь бид зөвхөн тугийг шинэчилж, одоогийн элементийн индексийг туг болгон хадгалах болно. Нэг жишээг авч үзье.

Жишээ нь

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 хэвээр байгаа тул худал байна. Тиймээс оруулахгүй бол бид тугийг flag = 2 болгож шинэчлэх болно.

  • Дараагийн сонголт, i = 4, arr [i] = 8 байх үед туг нь -1-тэй тэнцүү биш бөгөөд arr [i] нь arr [flag] -тай тэнцэхгүй болно. Бид ижил дугаарыг дахин олж, түүний зайг олохгүйн тулд энэ нөхцлийг шалгаж байна.

Тэгэхээр одоо бид гаралтыг = 4 - 2 = 2 болгон шинэчлэх болно. Мөн flag = 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) нэмэлт зай шаарддаг.