מצא את המרחק המינימלי בין שני מספרים  


רמת קושי קַל
נשאל לעתים קרובות קופון דוניה Coursera מסירה מעבדות מונפרוג פייפאל Paytm Snapchat
מערך

הצהרת בעיה  

נתת מערך ושני מספרים הנקראים 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. אז זה לא ייכנס אם, רק נעדכן את הדגל כדגל = 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 יעודכן בפלט.

אז עכשיו יש לנו את המרחק המינימלי כ -1 בין אלמנט המערך arr [4] = 8 ו- arr [5] = 2.

ראה גם
גודל מערך משנה מקסימלי שווה ל- k

פלט = 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 (1) שטח נוסף.