Намерете минималното разстояние между две числа


Ниво на трудност Лесно
Често задавани в CouponDunia Coursera Делхейвъри Moonfrog Labs 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, а друго условие на индексите и същите елементи е станало false. След това просто ще актуализираме флага и ще съхраним текущия индекс на елемент във флаг. Нека разгледаме един пример и да разгледаме това:

Пример

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 [флаг]. Проверяваме това състояние, за да не намерим отново същия номер и да получим разстоянието му.

Така че сега ще актуализираме изхода като = 4 - 2 = 2. И също така ще актуализираме флаг = 4

  • Отново при i = 5, arr [i] = 2, ще намерим условието вярно, а също флагът не е равен на -1 и arr [i] не е равен на arr [флаг], така че ще актуализираме изхода отново като минимумът между min (4, 5-4) и 1 ще бъде актуализиран в изхода.

Така че сега имаме минималното разстояние като 1 между елемента на масива arr [4] = 8 и arr [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 (1) допълнително пространство.