ค้นหาค่าระยะทางระหว่างสองอาร์เรย์ Leetcode Solution


ระดับความยาก สะดวกสบาย
ถามบ่อยใน Uber
แถว

ปัญหาค้นหาค่าระยะห่างระหว่างสอง อาร์เรย์ Leetcode Solution มีอาร์เรย์สองอาร์เรย์ arr1 และ arr2 นอกเหนือจากอาร์เรย์ทั้งสองแล้วเรายังมีจำนวนเต็ม n จากนั้นปัญหาจะขอให้เราหาระยะห่างสัมพัทธ์ระหว่างอาร์เรย์สองอาร์เรย์ที่กำหนด ระยะทางสัมพัทธ์ถูกกำหนดให้เป็นจำนวนองค์ประกอบในอาร์เรย์แรกที่ไม่มีองค์ประกอบใด ๆ ในอาร์เรย์ที่สองที่มีความแตกต่างสัมบูรณ์ขั้นต่ำน้อยกว่าหรือเท่ากับจำนวนเต็ม d ที่กำหนด ดังนั้นก่อนที่จะดำน้ำลึกลงไปในการแก้ปัญหาก่อนอื่นเราควรดูตัวอย่างบางส่วนค้นหาค่าระยะทางระหว่างสองอาร์เรย์ Leetcode Solution

arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
2

คำอธิบาย: เราจะเลือกแต่ละองค์ประกอบทีละรายการจากอาร์เรย์แรกเพื่อตรวจสอบผลลัพธ์ สำหรับองค์ประกอบแรก 4 เราไม่มีองค์ประกอบที่เกี่ยวข้องในอาร์เรย์ที่สองที่มีความแตกต่างสัมบูรณ์ขั้นต่ำ 2 ด้วย เช่นเดียวกันสำหรับ 5 แต่ถ้าเราเห็นองค์ประกอบสุดท้าย 8 แสดงว่ามีองค์ประกอบที่มีค่าเดียวกันในอาร์เรย์ที่สอง ดังนั้น 8 จึงไม่ถือว่าเป็นคำตอบ ดังนั้นคำตอบจะกลายเป็น 2 เนื่องจาก 2 องค์ประกอบแรกของอาร์เรย์แรก

วิธีการ Brute force เพื่อค้นหาค่าระยะทางระหว่างอาร์เรย์สองอาร์เรย์ Leetcode Solution

วิธีแก้ปัญหาแบบเดรัจฉานสำหรับปัญหาเพียงแค่วนซ้ำทั้งอาร์เรย์ที่เลือกคู่ที่ไม่ซ้ำกัน จากนั้นคู่ที่ไม่ซ้ำกันเหล่านี้จะถูกตรวจสอบว่าความแตกต่างระหว่างคู่นั้นน้อยกว่าจำนวนเต็ม 'd' ที่กำหนดหรือไม่ หากความแตกต่างน้อยกว่า d เราจะตั้งค่าสถานะองค์ประกอบนั้น เราไม่นับองค์ประกอบที่ถูกตั้งค่าสถานะและจะส่งคืนจำนวนองค์ประกอบที่เหลือเป็นคำตอบ วิธีแก้ปัญหาค่อนข้างตรงไปตรงมา แต่อาจมีทางออกที่ดีกว่า

แนวทางที่ได้รับการปรับให้เหมาะสมเพื่อค้นหาค่าระยะห่างระหว่างสองอาร์เรย์ Leetcode Solution

ในแนวทางข้างต้นเราใช้สองลูปที่ซ้อนกัน แต่ในท้ายที่สุดเราจำเป็นต้องตรวจสอบว่าองค์ประกอบปัจจุบันในอาร์เรย์แรกมีองค์ประกอบเดียวในอาร์เรย์ที่สองที่มีความแตกต่างน้อยกว่า d หรือไม่ ดังนั้นถ้าเราเลือกสององค์ประกอบที่ใกล้เคียงที่สุดกับองค์ประกอบที่เลือกจากอาร์เรย์แรก หากองค์ประกอบที่ใกล้เคียงที่สุดทั้งสองนี้ไม่มีความแตกต่างสัมบูรณ์ขั้นต่ำน้อยกว่า d เราสามารถพูดได้ว่าไม่มีองค์ประกอบอื่นใดที่จะให้ผลลัพธ์ที่ดีกว่า

ดังนั้นปัญหาจึงเกิดขึ้นในการค้นหาสององค์ประกอบที่ใกล้เคียงที่สุด (จากอาร์เรย์ที่สอง) ไปยังองค์ประกอบที่เลือกของอาร์เรย์แรก ในการค้นหาองค์ประกอบที่ใกล้เคียงที่สุดทั้งสองนี้เราจัดเรียงอาร์เรย์ที่สองและใช้การค้นหาแบบไบนารี การใช้การค้นหาแบบไบนารีเราจะพบองค์ประกอบที่มีค่าเท่ากับหรือมากกว่าองค์ประกอบที่เลือก องค์ประกอบที่มีขนาดเล็กกว่าองค์ประกอบปัจจุบันยังใช้เพื่อประเมินความแตกต่าง

หากความแตกต่างเหล่านี้น้อยกว่า d เราจะตั้งค่าสถานะองค์ประกอบนั้นและไม่นับรวมในคำตอบ องค์ประกอบที่เหลือจะถูกนับรวมในคำตอบและจะถูกส่งกลับเมื่อสิ้นสุดฟังก์ชัน

โค้ดที่ปรับให้เหมาะสมเพื่อค้นหาค่าระยะทางระหว่างสองอาร์เรย์ Leetcode Solution

รหัส C ++

#include <bits/stdc++.h>
using namespace std;

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
    int ans = 0;
    sort(arr2.begin(), arr2.end());
    for(int i=0;i<arr1.size();i++){
        int it = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();
        bool isIt = false;
        if(it<arr2.size() && abs(arr2[it] - arr1[i]) <= d)isIt = true;
        if(it != 0 && abs(arr2[it-1] - arr1[i]) <= d)isIt = true;
        if(!isIt)
            ans++;
    }
    return ans;
}

int main(){
    vector<int> arr1 = {4,5,8};
    vector<int> arr2 = {10,9,1,8};
    int d = 2;
    cout<<findTheDistanceValue(arr1, arr2, d);
}
2

รหัส Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  private static int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int ans = 0;
        for (int i= 0;i<arr1.length;i++) {
            int it = Arrays.binarySearch(arr2, 0, arr2.length, arr1[i]);
            if (it < 0) it = -(it+1);
            boolean isIt = false;
            if(it<arr2.length && Math.abs(arr2[it] - arr1[i]) <= d)isIt = true;
            if(it != 0 && Math.abs(arr2[it-1] - arr1[i]) <= d)isIt = true;
            if(!isIt)
                ans++;
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] arr1 = {4,5,8};
      int[] arr2 = {10,9,1,8};
      int d = 2;
      System.out.print(findTheDistanceValue(arr1, arr2, d));
  }
}
2

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (สูงสุด (M, N) logN), เนื่องจากเราเรียงลำดับอาร์เรย์ที่สองและทำการค้นหาแบบไบนารีสำหรับแต่ละองค์ประกอบในอาร์เรย์แรก ในที่นี้ M, N คือจำนวนองค์ประกอบในอาร์เรย์ที่หนึ่งและที่สองตามลำดับ

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

บน), พื้นที่ที่ต้องการในการจัดเรียงอาร์เรย์ที่สอง