ຊອກຫາມູນຄ່າໄລຍະຫ່າງລະຫວ່າງສອງ Arrays Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Uber
Array

ປັນຫາພົບຄ່າໄລຍະຫ່າງລະຫວ່າງສອງ ອາເລ Leetcode Solution ໃຫ້ພວກເຮົາມີສອງຂບວນທີ່ຈະມາຮອດ arr1 ແລະ arr2. ຄຽງຄູ່ກັບສອງອາຄານ, ພວກເຮົາໄດ້ຖືກຈັດຫາດ້ວຍເລກ integer n. ຈາກນັ້ນບັນຫາກໍ່ຂໍໃຫ້ພວກເຮົາຊອກຫາໄລຍະຫ່າງທີ່ກ່ຽວຂ້ອງລະຫວ່າງສອງຂບວນທີ່ໃຫ້. ໄລຍະຫ່າງທີ່ກ່ຽວຂ້ອງຖືກ ກຳ ນົດເປັນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ ທຳ ອິດທີ່ບໍ່ມີອົງປະກອບໃດ ໜຶ່ງ ໃນແຖວທີສອງທີ່ມີຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງ ໜ້ອຍ ກວ່າຫຼືເທົ່າກັບ ຈຳ ນວນທີ່ໃຫ້ມາ ສະນັ້ນກ່ອນທີ່ຈະ ດຳ ນ້ ຳ ໃນການແກ້ໄຂຢ່າງເລິກເຊິ່ງ, ທຳ ອິດພວກເຮົາຄວນພິຈາລະນາເບິ່ງຕົວຢ່າງສອງສາມຢ່າງຊອກຫາມູນຄ່າໄລຍະຫ່າງລະຫວ່າງສອງ Arrays Leetcode Solution

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

ຄຳ ອະທິບາຍ: ພວກເຮົາຈະເລືອກເອົາແຕ່ລະອົງປະກອບແຕ່ລະອັນມາຈາກອັນດັບ ທຳ ອິດເພື່ອກວດສອບຜົນຜະລິດ. ສຳ ລັບອົງປະກອບ ທຳ ອິດ, 4 ພວກເຮົາບໍ່ມີສ່ວນປະກອບໃດ ໜຶ່ງ ທີ່ສອດຄ້ອງກັນໃນແຖວທີສອງທີ່ມີຄວາມແຕກຕ່າງຢ່າງ ໜ້ອຍ ສຸດຂອງ 2 ກັບມັນ. ມັນຈະຄືກັນ ສຳ ລັບ 5. ແຕ່ຖ້າພວກເຮົາເຫັນອົງປະກອບສຸດທ້າຍ, 8, ມັນກໍ່ມີອົງປະກອບ ໜຶ່ງ ທີ່ມີຄ່າດຽວກັນໃນແຖວທີສອງ. ດັ່ງນັ້ນ 8, ບໍ່ໄດ້ຖືກພິຈາລະນາເຂົ້າໄປໃນຄໍາຕອບ. ຄຳ ຕອບຈະກາຍເປັນ 2 ເທົ່າກັບ 2 ອັນເນື່ອງມາຈາກ XNUMX ອົງປະກອບຂອງແຖວ ທຳ ອິດ.

ວິທີການບັງຄັບໃຊ້ໄດ້ດີເພື່ອຊອກຫາມູນຄ່າໄລຍະຫ່າງລະຫວ່າງສອງ Arrays Leetcode Solution

ການແກ້ໄຂຜົນບັງຄັບໃຊ້ ສຳ ລັບບັນຫາແມ່ນງ່າຍດາຍ ສຳ ລັບອາຄານທັງສອງຄູ່ທີ່ເປັນເອກະລັກ. ຫຼັງຈາກນັ້ນ, ຄູ່ທີ່ເປັນເອກະລັກເຫຼົ່ານີ້ຈະຖືກກວດກາຖ້າຄວາມແຕກຕ່າງລະຫວ່າງພວກມັນ ໜ້ອຍ ກວ່າຕົວເລກເຕັມທີ່ 'd'. ຖ້າຄວາມແຕກຕ່າງ ໜ້ອຍ ກວ່າ d, ພວກເຮົາທຸງອົງປະກອບ. ພວກເຮົາບໍ່ນັບເອົາອົງປະກອບທີ່ຖືກທຸງແລະ ຄຳ ນັບ ສຳ ລັບສ່ວນປະກອບທີ່ເຫຼືອແມ່ນສົ່ງຄືນເປັນ ຄຳ ຕອບ. ວິທີແກ້ໄຂແມ່ນຂ້ອນຂ້າງໄປຂ້າງ ໜ້າ ແຕ່ວ່າມັນສາມາດມີວິທີແກ້ໄຂທີ່ດີກວ່າ.

ວິທີການທີ່ດີທີ່ສຸດເພື່ອຊອກຫາມູນຄ່າໄລຍະຫ່າງລະຫວ່າງສອງ Arrays Leetcode Solution

ໃນວິທີການຂ້າງເທິງ, ພວກເຮົາໄດ້ໃຊ້ສອງວົງແຫວນທີ່ມີຮັງ. ແຕ່ໃນທີ່ສຸດ, ພວກເຮົາພຽງແຕ່ຕ້ອງການກວດສອບວ່າປັດຈຸບັນທີ່ຢູ່ໃນຂບວນ ທຳ ອິດມີອົງປະກອບດຽວໃນແຖວທີສອງທີ່ມີຄວາມແຕກຕ່າງບໍ່ຕໍ່າກ່ວາ d. ດັ່ງນັ້ນ, ຖ້າພວກເຮົາເລືອກເອົາສອງອົງປະກອບທີ່ໃກ້ທີ່ສຸດໄປຫາອົງປະກອບທີ່ຖືກຄັດເລືອກຈາກຂບວນ ທຳ ອິດ. ຖ້າສອງອົງປະກອບທີ່ໃກ້ທີ່ສຸດນີ້ບໍ່ມີຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕໍ່າສຸດຫນ້ອຍກ່ວາ d, ດັ່ງນັ້ນພວກເຮົາສາມາດເວົ້າຢ່າງແນ່ນອນວ່າບໍ່ມີອົງປະກອບອື່ນໃດສາມາດສ້າງຜົນໄດ້ຮັບທີ່ດີກວ່ານີ້.

ດັ່ງນັ້ນ, ບັນຫາຕອນນີ້ຈະຕົ້ມໄປຫາການຊອກຫາສອງອົງປະກອບທີ່ໃກ້ທີ່ສຸດ (ຈາກແຖວທີສອງ) ໄປຫາອົງປະກອບທີ່ຖືກເກັບຂອງອາເລ ທຳ ອິດ. ເພື່ອຊອກຫາສອງອົງປະກອບທີ່ໃກ້ທີ່ສຸດນີ້, ພວກເຮົາຈັດຮຽງແຖວທີສອງແລະໃຊ້ການຄົ້ນຫາຖານສອງ. ການ ນຳ ໃຊ້ການຄົ້ນຫາຖານສອງພວກເຮົາພົບວ່າອົງປະກອບທີ່ເທົ່າກັບຫຼືໃຫຍ່ກວ່າທາດທີ່ຖືກເກັບ. ອົງປະກອບທີ່ມີຂະ ໜາດ ນ້ອຍກ່ວາປັດຈຸບັນກໍ່ຖືກ ນຳ ໃຊ້ເພື່ອປະເມີນຄວາມແຕກຕ່າງ.

ຖ້າຄວາມແຕກຕ່າງເຫຼົ່ານີ້ຕ່ ຳ ກວ່າ d ຫຼັງຈາກນັ້ນພວກເຮົາທຸງອົງປະກອບແລະບໍ່ນັບມັນຕໍ່ ຄຳ ຕອບ. ສ່ວນປະກອບທີ່ເຫຼືອແມ່ນນັບໄປສູ່ ຄຳ ຕອບແລະຖືກສົ່ງຄືນໃນຕອນທ້າຍຂອງ ໜ້າ ທີ່.

ລະຫັດທີ່ດີທີ່ສຸດເພື່ອຊອກຫາມູນຄ່າໄລຍະຫ່າງລະຫວ່າງສອງ Arrays 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 ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ ທຳ ອິດແລະທີສອງຕາມ ລຳ ດັບ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N), ຊ່ອງທີ່ຕ້ອງການເພື່ອຈັດຮຽງແຖວທີສອງ.