หาระยะห่างต่ำสุดระหว่างตัวเลขสองตัว


ระดับความยาก สะดวกสบาย
ถามบ่อยใน คูปอง Coursera เดลี Moonfrog Labs บัตรเครดิต/เดบิต หรือ 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

ผลลัพธ์ = ค่าสูงสุดของจำนวนเต็มแฟล็ก = - 1

เราให้ตัวเลขสองตัว x = 2 และ y = 8

  • i = 0 เราจะตรวจสอบว่า arr [i] เท่ากับ 2 หรือ arr [i] เท่ากับ 8 แต่เงื่อนไขไม่เป็นไปตามเงื่อนไข

เงื่อนไขเป็นไปตามเมื่อ i = 2

  • i = 2, arr [i] เท่ากับ 2

เราจะตรวจสอบแฟล็กและมันเป็นเท็จเนื่องจากแฟล็กยังคงเป็น -1 ดังนั้นมันจะไม่เข้าใน if เราจะอัปเดตแฟล็กเป็น flag = 2

  • เลือกถัดไปเมื่อ i = 4, arr [i] = 8 แฟล็กไม่เท่ากับ -1 และ arr [i] ไม่เท่ากับ arr [แฟล็ก] เรากำลังตรวจสอบเงื่อนไขนี้เพื่อไม่ให้พบหมายเลขเดิมอีกและได้ระยะทาง

ตอนนี้เราจะอัปเดตผลลัพธ์เป็น = 4 - 2 = 2 และอัปเดต flag = 4 ด้วย

  • อีกครั้งที่ i = 5, arr [i] = 2 เราจะพบเงื่อนไขเป็นจริงและแฟล็กไม่เท่ากับ -1 และ arr [i] ไม่เท่ากับ arr [แฟล็ก] ดังนั้นเราจะอัปเดตเอาต์พุตอีกครั้งเป็น ค่าต่ำสุดระหว่างนาที (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 (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์

ความซับซ้อนของอวกาศ

บน) ความซับซ้อนของพื้นที่เนื่องจากเราใช้อาร์เรย์เพื่อจัดเก็บอินพุต แต่อัลกอริทึมในการค้นหาระยะทางขั้นต่ำต้องใช้พื้นที่พิเศษ O (1)