दुई एर्रेको लेटकोड समाधानको बीच दूरी मान फेला पार्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ Uber
एरे

समस्या दुई बीच दूरी मान खोज्नुहोस् Arrays लेटकोड समाधानले हामीलाई दुई एर्रे एआर १ र एर २ प्रदान गर्दछ। दुई एर्रेको साथ, हामीसँग एक पूर्णांक एन प्रदान गरिन्छ। त्यसो भए समस्याले हामीलाई दुई दुई एर्रे बीचको सापेक्ष दूरी पत्ता लगाउन भन्यो। सापेक्ष दूरी पहिलो एर्रेमा एलिमेन्ट्सको संख्याको रूपमा परिभाषित गरिएको छ जुन दोस्रो एरेमा कुनै एलिमेन्ट छैन जुन न्यूनतम निरपेक्ष भिन्नता दिइएको इन्टिजर d भन्दा कम वा बराबर छ। त्यसोभए जहिले पनी समाधानमा गहिरो डाइभ गर्नु भन्दा पहिले हामीले केही उदाहरणहरू हेर्नु पर्छ।दुई एर्रेको लेटकोड समाधानको बीच दूरी मान फेला पार्नुहोस्

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

स्पष्टीकरण: हामी आउटपुट प्रमाणित गर्न प्रत्येक एर्रेमेन्ट पहिलो एरेबाट एक एक गरी छान्नेछौं। पहिलो एलिमेन्टका लागि 4 हामीसँग दोस्रो एरेमा कुनै पनि त्यस्तै तत्व छैन जुनसँग यसको न्यूनतम २ पूर्ण भिन्नता छ। समान 2. को लागि जान्छ। तर यदि हामीले अन्तिम एलिमेन्ट, देख्यौं भने त्यहाँ दोस्रो एरेमा समान मानको साथ एक एलिमेन्ट छ। यसैले,, उत्तरमा ध्यान दिइएन। उत्तर २ सँग बराबर हुनेछ किनकि पहिलो एर्रेको पहिलो २ तत्वहरूको कारण।

दुई एर्रे लीटकोड समाधानको बीच दूरी मान खोज्न ब्रुट बल दृष्टिकोण

समस्याको लागि बल बल समाधान अनन्य जोडीहरू लिने दुबै एर्रे माथि केवल पुनरावृत्ति गर्दछ। त्यसो भए यी अद्वितीय जोडीहरू जाँच गरिन्छ यदि ती दुई बीचको भिन्नता दिइएको पूर्णा'्क 'd' भन्दा कम छ भने। यदि भिन्नता d भन्दा कम छ भने, हामी तत्व फ्ल्याग गर्छौं। हामी झण्डा लगाईएका तत्त्वहरूलाई गणना गर्दैनौं र बाँकी तत्वहरूको गणना उत्तरको रूपमा फर्काइन्छ। समाधान निकै सिधा अगाडि छ तर त्यहाँ एक राम्रो समाधान हुन सक्छ।

दुई एर्रेको लेटकोड समाधानको बीच दूरी मान खोज्नका लागि अनुकूलित दृष्टिकोण

माथिको दृष्टिकोणमा, हामीले दुई नेस्टेड लूपहरू प्रयोग गर्‍यौं। तर अन्त्यमा, हामीले केवल यो जाँच गर्न आवश्यक छ कि पहिलो एर्रेमा हालको एलिमेन्ट पनि दोस्रो एरेमा एकल एलिमेन्ट छ कि d भन्दा कम फरक छ। त्यसो भए, यदि हामीले पहिलो एर्रेबाट दुईवटा निकट तत्त्वहरू छनौट गर्यौं। यदि यी दुई निकटतम तत्त्वहरूसँग d भन्दा न्यूनतम निरपेक्ष भिन्नता छैन भने, तब हामी निश्चित रूपमा भन्न सक्छौं कि कुनै अन्य तत्वले राम्रो परिणाम दिन सक्दैन।

त्यसो भए, समस्या अब दुई नजिकका तत्वहरू (दोस्रो एरेबाट) पत्ता लगाउनको लागि पहिलो एर्रेको उठाइएको तत्त्वमा उक्लिन्छ। यी दुई नजिकका तत्वहरू फेला पार्न हामी दोस्रो एर्रे क्रमबद्ध गर्दछौं र बाइनरी खोजी प्रयोग गर्दछौं। बाइनरी खोजको प्रयोगले हामी एलिमेन्ट फेला पार्छौं जुन छनौट तत्त्वको बराबर वा ठूलो छ। तत्त्व जुन अहिलेको तत्व भन्दा सानो छ यो पनि भिन्नता मूल्यांकन गर्न प्रयोग गरिन्छ।

यदि यी भिन्नता d भन्दा कम छन् भने हामी तत्वलाई फ्ल्याग गर्छौं र यसलाई उत्तर तिर गणना गर्दैनौं। बाँकी तत्त्वहरू उत्तर तिर गणना गरिन्छन् र समारोहको अन्त्यमा फिर्ता हुन्छन्।

दुई एर्रेको लेटकोड समाधानको बीच दूरी मान खोज्नका लागि अनुकूलित कोड

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

जावा कोड

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) लग एन, किनकि हामी दोस्रो एर्रे क्रमबद्ध गर्छौं र पहिलो एर्रेमा प्रत्येक एलिमेन्टको लागि बाइनरी खोजी गर्दछौं। यहाँ एम, एन क्रमशः पहिलो र दोस्रो एर्रेमा एलिमेन्ट्सको संख्या हो।

ठाउँ जटिलता

O (N), दोस्रो एर्रे क्रमबद्ध गर्न ठाउँ आवाश्यक हुन्छ।