రెండు శ్రేణుల లీట్‌కోడ్ పరిష్కారం మధ్య దూర విలువను కనుగొనండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది ఉబెర్
అర్రే

సమస్య రెండు మధ్య దూర విలువను కనుగొనండి వ్యూహాలను లీట్‌కోడ్ సొల్యూషన్ మాకు రెండు శ్రేణులను arr1 మరియు arr2 అందిస్తుంది. రెండు శ్రేణులతో పాటు, మనకు పూర్ణాంకం n అందించబడుతుంది. ఇచ్చిన రెండు శ్రేణుల మధ్య సాపేక్ష దూరాన్ని కనుగొనమని సమస్య అడుగుతుంది. సాపేక్ష దూరం మొదటి శ్రేణిలోని మూలకాల సంఖ్యగా నిర్వచించబడింది, ఇది రెండవ శ్రేణిలో ఏ మూలకాన్ని కలిగి ఉండదు, అది ఇచ్చిన పూర్ణాంకానికి తక్కువ లేదా సమానమైన కనీస సంపూర్ణ వ్యత్యాసం ఉంటుంది. కాబట్టి ఎప్పటిలాగే ద్రావణంలో లోతుగా డైవింగ్ చేసే ముందు, మొదట మనం కొన్ని ఉదాహరణలను పరిశీలించాలి.రెండు శ్రేణుల లీట్‌కోడ్ పరిష్కారం మధ్య దూర విలువను కనుగొనండి

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

వివరణ: అవుట్‌పుట్‌ను ధృవీకరించడానికి మేము ప్రతి శ్రేణిని మొదటి శ్రేణి నుండి ఒక్కొక్కటిగా ఎంచుకుంటాము. మొదటి మూలకం కోసం, 4 మనకు రెండవ శ్రేణిలో సంబంధిత మూలకం లేదు, దానితో కనీస సంపూర్ణ వ్యత్యాసం 2 ఉంటుంది. అదే 5 కి వెళుతుంది. కాని చివరి మూలకం 8 ను చూస్తే, రెండవ శ్రేణిలో అదే విలువ కలిగిన మూలకం ఉంది. అందువలన 8, జవాబుగా పరిగణించబడదు. మొదటి శ్రేణి యొక్క మొదటి 2 మూలకాల కారణంగా సమాధానం 2 కి సమానంగా ఉంటుంది.

రెండు శ్రేణుల లీట్‌కోడ్ పరిష్కారం మధ్య దూర విలువను కనుగొనడానికి బ్రూట్ ఫోర్స్ అప్రోచ్

సమస్యకు బ్రూట్ ఫోర్స్ పరిష్కారం ప్రత్యేకమైన జతలను ఎంచుకునే రెండు శ్రేణులపై మళ్ళిస్తుంది. ఈ ప్రత్యేక జతలు వాటి మధ్య వ్యత్యాసం ఇచ్చిన పూర్ణాంకం 'd' కన్నా తక్కువగా ఉందో లేదో తనిఖీ చేయబడతాయి. వ్యత్యాసం d కంటే తక్కువగా ఉంటే, మేము మూలకాన్ని ఫ్లాగ్ చేస్తాము. మేము ఫ్లాగ్ చేసిన మూలకాలను లెక్కించము మరియు మిగిలిన మూలకాలకు కౌంట్ జవాబుగా తిరిగి ఇవ్వబడుతుంది. పరిష్కారం చాలా సరళంగా ముందుకు ఉంటుంది కాని మంచి పరిష్కారం ఉంటుంది.

రెండు శ్రేణుల లీట్‌కోడ్ పరిష్కారం మధ్య దూర విలువను కనుగొనడానికి ఆప్టిమైజ్ చేసిన విధానం

పై విధానంలో, మేము రెండు సమూహ ఉచ్చులను ఉపయోగించాము. కానీ చివరికి, మొదటి శ్రేణిలోని ప్రస్తుత మూలకం రెండవ శ్రేణిలో ఒకే మూలకాన్ని కలిగి ఉందో లేదో మాత్రమే తనిఖీ చేయాలి, అది d కంటే తక్కువ వ్యత్యాసాన్ని కలిగి ఉంటుంది. కాబట్టి, మేము మొదటి శ్రేణి నుండి ఎంచుకున్న మూలకానికి రెండు దగ్గరి అంశాలను ఎంచుకుంటే. ఈ రెండు దగ్గరి మూలకాలకు d కన్నా తక్కువ సంపూర్ణ వ్యత్యాసం లేకపోతే, ఇతర మూలకాలు మంచి ఫలితాన్ని ఇవ్వలేవని మనం ఖచ్చితంగా చెప్పగలం.

కాబట్టి, సమస్య ఇప్పుడు రెండు దగ్గరి మూలకాలను (రెండవ శ్రేణి నుండి) మొదటి శ్రేణి యొక్క ఎంచుకున్న మూలకానికి కనుగొనటానికి దిమ్మదిరుగుతుంది. ఈ రెండు దగ్గరి అంశాలను కనుగొనడానికి, మేము రెండవ శ్రేణిని క్రమబద్ధీకరిస్తాము మరియు బైనరీ శోధనను ఉపయోగిస్తాము. బైనరీ శోధనను ఉపయోగించి ఎంచుకున్న మూలకం కంటే సమానమైన లేదా అంతకంటే ఎక్కువ మూలకాన్ని మేము కనుగొంటాము. ప్రస్తుత మూలకం కంటే చిన్నదిగా ఉన్న మూలకం వ్యత్యాసాన్ని అంచనా వేయడానికి కూడా ఉపయోగించబడుతుంది.

ఈ తేడాలు d కన్నా తక్కువగా ఉంటే, అప్పుడు మేము మూలకాన్ని ఫ్లాగ్ చేస్తాము మరియు దానిని సమాధానం వైపు లెక్కించము. మిగిలిన అంశాలు సమాధానం వైపు లెక్కించబడతాయి మరియు ఫంక్షన్ చివరిలో తిరిగి ఇవ్వబడతాయి.

రెండు శ్రేణుల లీట్‌కోడ్ పరిష్కారం మధ్య దూర విలువను కనుగొనడానికి ఆప్టిమైజ్ కోడ్

సి ++ కోడ్

#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

జావా కోడ్

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 వరుసగా మొదటి మరియు రెండవ శ్రేణిలోని మూలకాల సంఖ్య.

అంతరిక్ష సంక్లిష్టత

పై), రెండవ శ్రేణిని క్రమబద్ధీకరించడానికి స్థలం అవసరం.