געפֿינען די ווייַטקייט ווערט צווישן צוויי אַרייז Leetcode סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין ובער
מענגע

די פּראָבלעם געפֿינען די ווייַטקייט ווערט צווישן צוויי Arrays Leetcode סאַלושאַן גיט אונדז צוויי ערייז arr1 און arr2. צוזאמען מיט די צוויי ערייז, מיר זענען צוגעשטעלט מיט אַ גאַנץ נומער n. דער פּראָבלעם בעטן אונדז צו געפֿינען די קאָרעוו ווייַטקייט צווישן די צוויי ערייז. די קאָרעוו ווייַטקייט איז דיפיינד ווי די נומער פון עלעמענטן אין דער ערשטער מענגע וואָס האט קיין עלעמענט אין די רגע מענגע וואָס האט אַ מינימום אַבסאָלוט חילוק ווייניקער ווי אָדער גלייַך צו די געגעבן גאַנץ נומער ד. ווי שטענדיק איידער דייווינג טיף אין דער לייזונג, מיר זאָל נעמען אַ ביסל ביישפילן.געפֿינען די ווייַטקייט ווערט צווישן צוויי אַרייז Leetcode סאַלושאַן

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

דערקלערונג: מיר וועלן קלייַבן יעדער עלעמענט איינער פֿאַר איינער פון די ערשטער מענגע צו באַשטעטיקן די פּראָדוקציע. פֿאַר דער ערשטער עלעמענט 4 מיר טאָן ניט האָבן קיין קאָראַספּאַנדינג עלעמענט אין די רגע מענגע מיט אַ מינימום אַבסאָלוט חילוק פון 2. דער זעלביקער גייט פֿאַר 5. אבער אויב מיר זען די לעצטע עלעמענט, 8, עס איז אַן עלעמענט מיט דער זעלביקער ווערט אין די רגע מענגע. אזוי, 8 איז ניט באטראכט אין דער ענטפער. דער ענטפער וועט ווערן גלייַך צו 2 ווייַל פון די ערשטע 2 יסודות פון דער ערשטער מענגע.

ברוט קראַפט אַפּפּראָאַטש צו געפֿינען די ווייַטקייט ווערט צווישן צוויי אַרייז Leetcode סאַלושאַן

די ברוט קראַפט לייזונג פֿאַר דעם פּראָבלעם איז נאָר יטעראַטעס ביי ביידע ערייז צו קלייַבן יינציק פּערז. דערנאָך די יינציק פּערז זענען אָפּגעשטעלט אויב די חילוק צווישן זיי איז ווייניקער ווי די געגעבן גאַנץ נומער 'ד'. אויב די חילוק איז ווייניקער ווי ד, מיר פלאַגינג די עלעמענט. מיר טאָן ניט ציילן די פלאַגד עלעמענטן און דער ציילן פֿאַר די רוען עלעמענטן איז אומגעקערט ווי די ענטפער. די לייזונג איז שיין גלייך פאָרויס אָבער עס קען זיין אַ בעסער לייזונג.

אָפּטימיזעד אַפּפּראָאַטש צו געפֿינען די ווייַטקייט ווערט צווישן צוויי אַרייז Leetcode סאַלושאַן

אין דעם אויבן צוגאַנג, מיר געוויינט צוויי נעסטעד לופּס. צום סוף, מיר נאָר דאַרפֿן צו קאָנטראָלירן אויב די קראַנט עלעמענט אין דער ערשטער מענגע האט אפילו אַ איין עלעמענט אין די רגע מענגע וואָס האט אַ חילוק פון ווייניקער ווי ד. אַזוי, אויב מיר קלייַבן די צוויי קלאָוסאַסט עלעמענטן צו דער פּיקט עלעמענט פֿון דער ערשטער מענגע. אויב די צוויי קלאָוסאַסט עלעמענטן טאָן ניט האָבן אַ מינימום אַבסאָלוט חילוק פון ווייניקער ווי d, מיר קענען זאָגן פֿאַר זיכער אַז קיין אנדערע עלעמענט קענען פּראָדוצירן אַ בעסער רעזולטאַט.

דער פּראָבלעם איז איצט צו געפֿינען די צוויי קלאָוסאַסט עלעמענטן (פֿון די רגע מענגע) צו די פּיקט עלעמענט פון דער ערשטער מענגע. צו געפֿינען די צוויי קלאָוסאַסט עלעמענטן, מיר סאָרט די רגע מענגע און נוצן ביינערי זוכן. ניצן ביינערי זוכן מיר געפֿינען די עלעמענט וואָס איז גלייַך אָדער גרעסער ווי די פּיקט עלעמענט. דער עלעמענט וואָס איז נאָר קלענערער ווי די קראַנט עלעמענט איז אויך געניצט צו אָפּשאַצן די חילוק.

אויב די דיפראַנסאַז זענען ווייניקער ווי ד, מיר צייכן די עלעמענט און טאָן ניט רעכענען עס פֿאַר די ענטפער. די מנוחה עלעמענטן זענען גערעכנט אין דעם ענטפער און זענען אומגעקערט אין די סוף פון די פונקציע.

אָפּטימיזעד קאָד צו געפֿינען די ווייַטקייט ווערט צווישן צוויי אַרייז Leetcode סאַלושאַן

C ++ קאָד

#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

Java קאָד

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) לאָגן), זינט מיר סאָרט די רגע מענגע און דורכפירן אַ ביינערי זוכן פֿאַר יעדער עלעמענט אין דער ערשטער מענגע. דאָ M, N איז די נומער פון עלעמענטן אין דער ערשטער און רגע מענגע ריספּעקטיוולי.

ספעיס קאַמפּלעקסיטי

אָ (N), פּלאַץ פארלאנגט צו סאָרט די רגע מענגע.