ಎರಡು ಅರೇಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ನಡುವಿನ ಅಂತರ ಮೌಲ್ಯವನ್ನು ಹುಡುಕಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಉಬರ್
ಅರೇ

ಸಮಸ್ಯೆ ಎರಡು ನಡುವಿನ ಅಂತರ ಮೌಲ್ಯವನ್ನು ಹುಡುಕಿ ಅರೇಗಳು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ನಮಗೆ ಎರಡು ಸರಣಿಗಳನ್ನು arr1 ಮತ್ತು arr2 ಒದಗಿಸುತ್ತದೆ. ಎರಡು ಸರಣಿಗಳ ಜೊತೆಗೆ, ನಮಗೆ ಒಂದು ಪೂರ್ಣಾಂಕ n ಅನ್ನು ಒದಗಿಸಲಾಗಿದೆ. ಕೊಟ್ಟಿರುವ ಎರಡು ಸರಣಿಗಳ ನಡುವಿನ ಸಾಪೇಕ್ಷ ಅಂತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಮಸ್ಯೆ ನಮ್ಮನ್ನು ಕೇಳುತ್ತದೆ. ಸಾಪೇಕ್ಷ ಅಂತರವನ್ನು ಮೊದಲ ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ, ಅದು ಎರಡನೇ ಶ್ರೇಣಿಯಲ್ಲಿ ಯಾವುದೇ ಅಂಶವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ, ಅದು ಕನಿಷ್ಟ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವನ್ನು ನಿರ್ದಿಷ್ಟ ಪೂರ್ಣಾಂಕಕ್ಕಿಂತ ಕಡಿಮೆ ಅಥವಾ ಸಮನಾಗಿರುತ್ತದೆ d. ಆದ್ದರಿಂದ ಯಾವಾಗಲೂ ದ್ರಾವಣದಲ್ಲಿ ಆಳವಾಗಿ ಧುಮುಕುವ ಮೊದಲು, ಮೊದಲು ನಾವು ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡಬೇಕು.ಎರಡು ಅರೇಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ನಡುವಿನ ಅಂತರ ಮೌಲ್ಯವನ್ನು ಹುಡುಕಿ

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

ವಿವರಣೆ: .ಟ್‌ಪುಟ್ ಅನ್ನು ಪರಿಶೀಲಿಸಲು ನಾವು ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಮೊದಲ ಶ್ರೇಣಿಯಿಂದ ಒಂದೊಂದಾಗಿ ಆರಿಸಿಕೊಳ್ಳುತ್ತೇವೆ. ಮೊದಲ ಅಂಶಕ್ಕಾಗಿ, 4 ಎರಡನೇ ಶ್ರೇಣಿಯಲ್ಲಿ ಯಾವುದೇ ಅನುಗುಣವಾದ ಅಂಶವನ್ನು ನಾವು ಹೊಂದಿಲ್ಲ, ಅದು ಕನಿಷ್ಠ 2 ರೊಂದಿಗೆ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಅದೇ 5 ಕ್ಕೆ ಹೋಗುತ್ತದೆ. ಆದರೆ ನಾವು ಕೊನೆಯ ಅಂಶವಾದ 8 ಅನ್ನು ನೋಡಿದರೆ, ಎರಡನೇ ಶ್ರೇಣಿಯಲ್ಲಿ ಒಂದೇ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ಒಂದು ಅಂಶವಿದೆ. ಹೀಗೆ 8, ಅನ್ನು ಉತ್ತರವಾಗಿ ಪರಿಗಣಿಸಲಾಗುವುದಿಲ್ಲ. ಮೊದಲ ರಚನೆಯ ಮೊದಲ 2 ಅಂಶಗಳಿಂದಾಗಿ ಉತ್ತರವು 2 ಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ.

ಎರಡು ಅರೇಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ನಡುವಿನ ಅಂತರ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಲು ವಿವೇಚನಾರಹಿತ ವಿಧಾನ

ಸಮಸ್ಯೆಯ ವಿವೇಚನಾರಹಿತ ಪರಿಹಾರವು ವಿಶಿಷ್ಟ ಜೋಡಿಗಳನ್ನು ಆರಿಸುವ ಎರಡೂ ಸರಣಿಗಳ ಮೇಲೆ ಸರಳವಾಗಿ ಪುನರಾವರ್ತಿಸುತ್ತದೆ. ಈ ಅನನ್ಯ ಜೋಡಿಗಳನ್ನು ಅವುಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸವು ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕ 'ಡಿ' ಗಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ ಪರಿಶೀಲಿಸಲಾಗುತ್ತದೆ. ವ್ಯತ್ಯಾಸವು 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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಗರಿಷ್ಠ (ಎಂ, ಎನ್) ಲಾಗ್ಎನ್), ಏಕೆಂದರೆ ನಾವು ಎರಡನೇ ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸುತ್ತೇವೆ ಮತ್ತು ಮೊದಲ ಶ್ರೇಣಿಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಮಾಡುತ್ತೇವೆ. ಇಲ್ಲಿ M, N ಕ್ರಮವಾಗಿ ಮೊದಲ ಮತ್ತು ಎರಡನೆಯ ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಎರಡನೇ ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸಲು ಸ್ಥಳಾವಕಾಶ ಅಗತ್ಯವಿದೆ.