രണ്ട് അറേ ലീറ്റ്കോഡ് പരിഹാരങ്ങൾക്കിടയിലുള്ള ദൂരം കണ്ടെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു യൂബർ
അറേ

രണ്ടിനുമിടയിലുള്ള ദൂര മൂല്യം കണ്ടെത്തുക എന്നതാണ് പ്രശ്നം അറേ Leetcode Solution ഞങ്ങൾക്ക് 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 ആണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), രണ്ടാമത്തെ അറേ അടുക്കാൻ സ്ഥലം ആവശ്യമാണ്.