අරා දෙකක් ලීට්කෝඩ් විසඳුම අතර දුර අගය සොයා ගන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ Uber
අරා

ගැටළුව දෙකක් අතර දුර අගය සොයා ගන්න අරා ලීට්කෝඩ් විසඳුම අපට arr1 සහ arr2 අරා දෙකක් සපයයි. අරා දෙක සමඟ, අපට පූර්ණ සංඛ්‍යාවක් n ලබා දී ඇත. එවිට ගැටළුව අපෙන් ලබා දී ඇති අරා දෙක අතර සාපේක්ෂ දුර සොයා ගැනීමට අසයි. සාපේක්ෂ දුර අර්ථ දක්වනුයේ පළමු අරාවෙහි මූලද්‍රව්‍ය ගණන දෙවන අරාවෙහි කිසිදු මූලද්‍රව්‍යයක් නොමැති අවම නිරපේක්ෂ වෙනසක් ලබා දී ඇති පූර්ණ සංඛ්‍යාවට වඩා අඩු හෝ සමාන වේ. එබැවින් සෑම විටම විසඳුම ගැඹුරට කිමිදීමට පෙර, පළමුව අපි උදාහරණ කිහිපයක් දෙස බැලිය යුතුය.අරා දෙකක් ලීට්කෝඩ් විසඳුම අතර දුර අගය සොයා ගන්න

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

පැහැදිලි කිරීම: ප්‍රතිදානය සත්‍යාපනය කිරීම සඳහා අපි පළමු අරා සිට එක් එක් මූලද්‍රව්‍ය එකින් එක තෝරා ගනිමු. පළමු මූලද්‍රව්‍යය සඳහා, 4 අපට දෙවන අරාවෙහි අනුරූපී මූලද්‍රව්‍යයක් නොමැත, එය සමඟ අවම නිරපේක්ෂ වෙනසක් 2 ක් ඇත. 5 ට සමාන වේ. නමුත් අවසාන මූලද්‍රව්‍යය වන 8 නම්, දෙවන අරාවෙහි එකම අගය සහිත මූලද්‍රව්‍යයක් පවතී. මේ අනුව 8, පිළිතුර ලෙස නොසැලකේ. පළමු අරාවේ පළමු මූලද්‍රව්‍ය 2 නිසා පිළිතුර 2 ට සමාන වේ.

අරා දෙකක් ලීට්කෝඩ් විසඳුම අතර දුර අගය සොයා ගැනීමට තිරිසන් බලවේගය

ගැටළුව සඳහා තිරිසන් බල විසඳුම අද්විතීය යුගල තෝරා ගන්නා අරා දෙකටම වඩා වෙනස් වේ. මෙම අද්විතීය යුගල ලබා දී ඇති සංඛ්‍යා 'd' ට වඩා අඩු දැයි පරීක්ෂා කරනු ලැබේ. වෙනස d ට වඩා අඩු නම්, අපි මූලද්‍රව්‍යය සලකුණු කරමු. අපි සලකුණු කළ මූලද්‍රව්‍යයන් ගණන් නොගන්නා අතර ඉතිරි මූලද්‍රව්‍ය සඳහා ගණන් කිරීම පිළිතුර ලෙස ආපසු ලබා දෙනු ලැබේ. විසඳුම තරමක් forward ජුව ඉදිරියට ඇති නමුත් වඩා හොඳ විසඳුමක් තිබිය හැකිය.

අරා දෙකක් ලීට්කෝඩ් විසඳුම අතර දුර අගය සොයා ගැනීම සඳහා ප්‍රශස්ත ප්‍රවේශය

ඉහත ප්‍රවේශයේදී අපි කූඩු ලූප දෙකක් භාවිතා කළෙමු. නමුත් අවසානයේදී, අපට අවශ්‍ය වූයේ පළමු අරාවෙහි වත්මන් මූලද්‍රව්‍යයට දෙවන අරාවෙහි තනි මූලද්‍රව්‍යයක් හෝ 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 යනු පිළිවෙලින් පළමු හා දෙවන අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

මත), දෙවන අරාව වර්ග කිරීමට අවශ්‍ය අවකාශය.