બે એરે લીટકોડ સોલ્યુશન વચ્ચેનું અંતર મૂલ્ય શોધો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ઉબેર
અરે

સમસ્યા બે વચ્ચેનું અંતર મૂલ્ય શોધો એરેઝ લીટકોડ સોલ્યુશન આપણને બે એરે એઆર 1 અને એઆર 2 પ્રદાન કરે છે. બે એરેની સાથે, અમને પૂર્ણાંક એન આપવામાં આવે છે. પછી સમસ્યા અમને આપેલ બે એરે વચ્ચેનો સાપેક્ષ અંતર શોધવા માટે કહે છે. સંબંધિત અંતર એ પ્રથમ એરેમાં તત્વોની સંખ્યા તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જેમાં બીજા એરેમાં કોઈ ઘટક નથી જે આપેલ પૂર્ણાંક ડી કરતા ઓછું અથવા તેના કરતા ઓછું ન્યૂનતમ ચોક્કસ તફાવત ધરાવે છે. તેથી હંમેશાં ઉકેલમાં dંડે ડાઇવ કરતા પહેલાં, પહેલા આપણે થોડા ઉદાહરણો પર એક નજર નાખવી જોઈએ.બે એરે લીટકોડ સોલ્યુશન વચ્ચેનું અંતર મૂલ્ય શોધો

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

સમજૂતી: આઉટપુટને ચકાસવા માટે અમે દરેક એલિમેન્ટને પ્રથમ એરેમાંથી એક પછી એક પસંદ કરીશું. પ્રથમ તત્વ માટે, 4 અમારી પાસે બીજા એરેમાં કોઈ અનુરૂપ તત્વ નથી જેની સાથે તેની સાથે ન્યૂનતમ 2 નો તફાવત છે. 5 પણ સમાન છે. પરંતુ જો આપણે છેલ્લું તત્વ 8 જોશું તો બીજા એરેમાં સમાન મૂલ્ય ધરાવતું એક તત્વ અસ્તિત્વમાં છે. આમ 8, જવાબમાં ધ્યાનમાં લેવામાં આવતાં નથી. પ્રથમ એરેના પ્રથમ 2 તત્વોને કારણે આ રીતે જવાબ 2 ની બરાબર થઈ જશે.

બે એરે લીટકોડ સોલ્યુશન વચ્ચેનું અંતર મૂલ્ય શોધવા માટે જડ બળનો અભિગમ

સમસ્યાનું ઘાતક બળ નિવારણ અનન્ય જોડીને ચૂંટતા બંને એરે પર સરળતાથી ફરી વળે છે. પછી આ અનન્ય જોડી તપાસવામાં આવે છે જો આપેલ પૂર્ણાંક 'ડી' કરતાં તેમની વચ્ચેનો તફાવત ઓછો હોય તો. જો તફાવત ડી કરતા ઓછો હોય, તો અમે તત્વને ફ્લેગ કરીએ છીએ. અમે ફ્લેગ કરેલા તત્વોની ગણતરી કરતા નથી અને બાકીના તત્વોની ગણતરી જવાબ તરીકે પરત આવે છે. સોલ્યુશન એકદમ સીધું આગળ છે પરંતુ આનાથી સારો ઉપાય હોઈ શકે છે.

બે એરે લીટકોડ સોલ્યુશન વચ્ચેનું અંતર મૂલ્ય શોધવા માટે Opપ્ટિમાઇઝ અભિગમ

ઉપરોક્ત અભિગમમાં, અમે બે નેસ્ડ લૂપ્સનો ઉપયોગ કર્યો. પરંતુ અંતે, આપણે ફક્ત એ જ તપાસવાની જરૂર હતી કે પહેલા એરેમાં વર્તમાન તત્વ બીજા એરેમાં પણ એક ઘટક છે કે જેમાં ડી કરતાં ઓછો તફાવત છે. તેથી, જો આપણે પહેલા એરેમાંથી ચૂંટાયેલા તત્વ માટેના બે નજીકના તત્વોને પસંદ કરીએ. જો આ બે નજીકના તત્વોમાં ડી કરતાં ઓછો લઘુત્તમ સંપૂર્ણ તફાવત ન હોય, તો અમે ખાતરીથી કહી શકીએ કે કોઈ અન્ય તત્વ વધુ સારું પરિણામ આપી શકશે નહીં.

તેથી, સમસ્યા હવે પ્રથમ એરેના ચૂંટેલા ઘટકમાં (બીજા એરેથી) નજીકના બે તત્વો શોધવા માટે ઉકળે છે. આ બે નજીકના તત્વો શોધવા માટે, અમે બીજો એરે સ sortર્ટ કરીએ છીએ અને બાઈનરી શોધનો ઉપયોગ કરીએ છીએ. દ્વિસંગી શોધનો ઉપયોગ કરીને અમને તે તત્વ મળે છે જે ચૂંટેલા તત્વ કરતાં સમાન અથવા વધારે હોય છે. વર્તમાન તત્વની તુલનામાં નાનું તત્વ પણ તફાવતનું મૂલ્યાંકન કરવા માટે વપરાય છે.

જો આ તફાવતો ડી કરતા ઓછા હોય તો આપણે તત્વને ચિહ્નિત કરીએ છીએ અને તેને જવાબ તરફ ગણીશું નહીં. બાકીના તત્વો જવાબ તરફ ગણવામાં આવે છે અને ફંક્શનના અંતે પરત આવે છે.

બે એરે લીટકોડ સોલ્યુશન વચ્ચેનું અંતર મૂલ્ય શોધવા માટે codeપ્ટિમાઇઝ કોડ

સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (મહત્તમ (એમ, એન) લNગએન), કારણ કે આપણે બીજા એરેને સ sortર્ટ કરીએ છીએ અને પ્રથમ એરેમાં દરેક તત્વ માટે દ્વિસંગી શોધ કરીએ છીએ. અહીં એમ, એન અનુક્રમે પ્રથમ અને બીજા એરેમાં તત્વોની સંખ્યા છે.

અવકાશ જટિલતા

ઓ (એન), બીજા એરેને સ sortર્ટ કરવા માટે જગ્યા આવશ્યક છે.