দুটি অ্যারে লেটকোড সমাধানের মধ্যে দূরত্বের মানটি সন্ধান করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় উবার
বিন্যাস

দু'জনের মধ্যে দূরত্বের মানটি আবিষ্কার করুন অ্যারেগুলির লেটকোড সলিউশন আমাদের দুটি অ্যারে অ্যারি 1 এবং এনার 2 সরবরাহ করে। দুটি অ্যারে পাশাপাশি, আমরা একটি পূর্ণসংখ্যা এন সরবরাহ করা হয়। তারপরে সমস্যাটি আমাদের প্রদত্ত দুটি অ্যারের মধ্যে আপেক্ষিক দূরত্ব খুঁজতে বলেছে। আপেক্ষিক দূরত্বটিকে প্রথম অ্যারেতে উপাদানগুলির সংখ্যা হিসাবে সংজ্ঞায়িত করা হয় যা দ্বিতীয় অ্যারেতে এমন কোনও উপাদান নেই যা প্রদত্ত পূর্ণসংখ্যার d বা তার চেয়ে কম বা তার সমান ন্যূনতম পরম পার্থক্য রাখে। সুতরাং সমাধানের গভীরে ডুব দেওয়ার আগে সর্বদা প্রথমে কয়েকটি উদাহরণ লক্ষ্য করা উচিত।দুটি অ্যারে লেটকোড সমাধানের মধ্যে দূরত্বের মানটি সন্ধান করুন

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

ব্যাখ্যা: আউটপুট যাচাই করতে আমরা প্রতিটি অ্যারেটিকে প্রথম অ্যারে থেকে এক এক করে বেছে নেব। প্রথম উপাদানটির জন্য, 4 আমাদের দ্বিতীয় অ্যারেতে কোনও আনুষঙ্গিক উপাদান নেই যা এর সাথে 2 এর সর্বনিম্ন পরম পার্থক্য রাখে। একই 5 এর জন্য যায়। তবে আমরা যদি শেষ উপাদানটি 8 দেখতে পাই তবে দ্বিতীয় অ্যারেতে একই মান সহ একটি উপাদান বিদ্যমান। সুতরাং 8, উত্তরের বিবেচনা করা হয় না। প্রথম অ্যারের প্রথম 2 উপাদানগুলির কারণে উত্তরটি 2 এর সমান হয়ে যাবে।

দু'টি অ্যারে লেটকোড সমাধানের মধ্যে দূরত্বের মান সন্ধানের জন্য জোর বল প্রয়োগ করুন

সমস্যার জন্য নিষ্ঠুর বলের সমাধানটি উভয় অ্যারে অনন্য জোড়া বাছাই করে কেবল পুনরাবৃত্তি করে। তারপরে প্রদত্ত পূর্ণসংখ্যা '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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (সর্বোচ্চ (এম, এন) লগএন), যেহেতু আমরা দ্বিতীয় অ্যারে বাছাই করি এবং প্রথম অ্যারেতে প্রতিটি উপাদানগুলির জন্য বাইনারি অনুসন্ধান করি perform এখানে এম, এন যথাক্রমে প্রথম এবং দ্বিতীয় অ্যারের উপাদানগুলির সংখ্যা।

স্পেস জটিলতা ity

চালু), দ্বিতীয় অ্যারে বাছাই করার জন্য স্থান প্রয়োজন।