Գտեք երկու զանգվածների Leetcode լուծույթի միջև հեռավորության արժեքը  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Uber
ալգորիթմները Դասավորություն կոդավորում հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions

Խնդիրը Գտեք Երկուսի միջև հեռավորության արժեքը Մուլտեր Leetcode Solution- ը մեզ տրամադրում է երկու arr1 և arr2 զանգված: Երկու զանգվածների հետ մեկտեղ մեզ տրամադրվում է n ամբողջ թիվ: Հետո խնդիրը խնդրում է մեզ գտնել տվյալ երկու զանգվածների հարաբերական հեռավորությունը: Հարաբերական հեռավորությունը սահմանվում է որպես առաջին զանգվածի տարրերի քանակ, որը երկրորդ զանգվածում չունի որևէ տարր, որն ունի նվազագույն բացարձակ տարբերություն `տրված ամբողջ թվից փոքր կամ հավասար d: Այսպիսով, ինչպես միշտ լուծման մեջ խորասուզվելուց առաջ, նախ պետք է մի քանի օրինակ նայել:Գտեք երկու զանգվածների Leetcode լուծույթի միջև հեռավորության արժեքըPin

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

Բացատրություն. Արդյունքը ստուգելու համար մենք յուրաքանչյուր զանգվածը մեկ առ մեկ կընտրենք առաջին զանգվածից: Առաջին տարրի համար 4, երկրորդ զանգվածում մենք չունենք որևէ համապատասխան տարր, որն իր հետ ունենա նվազագույն բացարձակ 2 տարբերություն: Նույնը վերաբերում է 5. Բայց եթե մենք տեսնում ենք վերջին ՝ 8 տարրը, երկրորդ զանգվածում գոյություն ունի նույն արժեք ունեցող տարր: Այսպիսով, 8-ը չի դիտարկվում որպես պատասխան: Այսպիսով, պատասխանը կդառնա 2-ի `առաջին զանգվածի առաջին 2 տարրերի պատճառով:

Բառը

Brute force մոտեցում ՝ գտնելու երկու զանգվածների Leetcode լուծույթի միջև հեռավորության արժեքը  

Խնդրի բիրտ ուժի լուծումը պարզապես կրկնվում է ինչպես զանգվածների վրա, այնպես էլ հավաքում են եզակի զույգեր: Ապա այս եզակի զույգերը ստուգվում են, եթե նրանց միջև տարբերությունը պակաս է տրված 'd' ամբողջ թվից: Եթե ​​տարբերությունը d- ից փոքր է, մենք դրոշը տալիս ենք տարրին: Մենք չենք հաշվում դրոշավորված տարրերը, իսկ մնացած տարրերի քանակը վերադարձվում է որպես պատասխան: Լուծումը բավականին ուղիղ առաջ է, բայց կարող է լինել ավելի լավ լուծում:

Երկու զանգվածների Leetcode լուծույթի միջև հեռավորության արժեքը գտնելու օպտիմիզացված մոտեցում  

Վերոնշյալ մոտեցման մեջ մենք օգտագործեցինք երկու տեղադրված օղակ: Բայց, ի վերջո, մեզ միայն անհրաժեշտ էր ստուգել, ​​արդյոք առաջին զանգվածի ներկայիս տարրը երկրորդ զանգվածում ունի նույնիսկ մեկ տարր, որն ունի d- ից պակաս տարբերություն: Այսպիսով, եթե ընտրենք առաջին զանգվածից ընտրված տարրի երկու ամենամոտ տարրերը: Եթե ​​այս երկու ամենամոտ տարրերը չունեն d- ից պակաս նվազագույն բացարձակ տարբերություն, ապա հաստատ կարող ենք ասել, որ ոչ մի այլ տարր չի կարող ավելի լավ արդյունք տալ:

Այսպիսով, խնդիրն այժմ ընկնում է մինչև գտնելու երկու ամենամոտ տարրերը (երկրորդ զանգվածից) մինչև առաջին զանգվածի ընտրված տարրը: Այս երկու ամենամոտ տարրերը գտնելու համար մենք դասավորում ենք երկրորդ զանգվածը և օգտագործում երկուական որոնում: Երկուական որոնման միջոցով մենք գտնում ենք տարրը, որը հավասար է կամ ավելի մեծ, քան ընտրված տարրը: Տարրը, որն ուղղակի փոքր է ներկայիս տարրից, օգտագործվում է նաև տարբերությունը գնահատելու համար:

Տես նաեւ,
Պատրաստիր լարը մեծ Leetcode լուծում

Եթե ​​այս տարբերությունները d- ից պակաս են, մենք դրոշը տալիս ենք տարրին և չենք հաշվում այն ​​պատասխանի նկատմամբ: Մնացած տարրերը հաշվվում են պատասխանի նկատմամբ և վերադարձվում են գործառույթի վերջում:

Օպտիմիզացված ծածկագիր `երկու զանգվածների Leetcode լուծույթի միջև հեռավորության արժեքը գտնելու համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (առավելագույն (M, N) logN), քանի որ մենք դասավորում ենք երկրորդ զանգվածը և կատարում յուրաքանչյուր զանգվածի երկուական որոնում առաջին զանգվածում: Այստեղ M, N համապատասխանաբար առաջին և երկրորդ զանգվածների տարրերի քանակն է:

Տիեզերական բարդություն

ՎՐԱ), երկրորդ զանգվածը տեսակավորելու համար պահանջվող տարածք: