Βρείτε την ελάχιστη απόσταση μεταξύ δύο αριθμών


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Κουπόνι Ντούνια Coursera Δελχί Εργαστήρια Moonfrog PayPal 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

Έξοδος = Μέγιστη τιμή ενός Ακέραιου, flag = - 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, το flag δεν είναι ίσο με -1 και επίσης το arr [i] δεν είναι ίσο με το arr [flag]. Ελέγχουμε αυτήν την κατάσταση, ώστε να μην βρούμε ξανά τον ίδιο αριθμό και να πάρουμε την απόστασή της.

Τώρα λοιπόν θα ενημερώσουμε την έξοδο ως = 4 - 2 = 2. Και επίσης θα ενημερώσουμε τη σημαία = 4

  • Και πάλι στο i = 5, arr [i] = 2, θα βρούμε την κατάσταση αληθινή και επίσης η σημαία δεν είναι ίση με -1 και η arr [i] δεν είναι ίση με arr [flag], οπότε θα ενημερώσουμε ξανά την έξοδο ως το ελάχιστο μεταξύ 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Το single traversal κάνει τον αλγόριθμο να λειτουργεί σε γραμμική πολυπλοκότητα χρόνου. O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

ΕΠΙ) πολυπλοκότητα χώρου αφού χρησιμοποιούμε έναν πίνακα για να αποθηκεύσουμε την είσοδο. Όμως ο αλγόριθμος για την εύρεση της ελάχιστης απόστασης απαιτεί O (1) επιπλέον χώρο.