இரண்டு வரிசைகள் லீட்கோட் தீர்வுக்கு இடையிலான தூர மதிப்பைக் கண்டறியவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது கிழித்து
அணி

சிக்கல் இரண்டுக்கும் இடையிலான தூர மதிப்பைக் கண்டறியவும் வரிசைகள் லீட்கோட் தீர்வு எங்களுக்கு இரண்டு வரிசைகள் 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 என்பது முறையே முதல் மற்றும் இரண்டாவது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது

ஓ (என்), இரண்டாவது வரிசையை வரிசைப்படுத்த இடம் தேவை.