Leitcode чечиминин эки массивдин ортосундагы аралыкты табыңыз


Кыйынчылык деңгээли жеңил
Көп суралган Uber
согуштук тизме

Маселе, экөөнүн ортосундагы аралыкты табуу Arrays Leetcode Solution бизге arr1 жана arr2 эки массивин берет. Эки массив менен катар бизге бүтүн n саны берилет. Андан кийин маселе бизге берилген эки массивдин ортосундагы салыштырмалуу аралыкты табууну сурайт. Салыштырмалуу аралык - экинчи массивде минималдуу абсолюттук айырмасы берилген d сандан кем же ага барабар эч кандай элементтери жок биринчи массивдеги элементтердин саны катары аныкталат. Ошентип, чечимге терең сүңгөөрдөн мурун, алгач бир нече мисалдарды карап көрүшүбүз керек.Leitcode чечиминин эки массивдин ортосундагы аралыкты табыңыз

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

Түшүндүрмө: Чыгууну текшерүү үчүн биринчи массивден ар бир элементти бир-бирден тандап алабыз. Биринчи элемент үчүн, 4 бизде экинчи массивде аны менен минималдуу абсолюттук айырмасы 2 болгон бир дагы тиешелүү элемент жок. Ошол эле нерсе 5ке тиешелүү. Бирок, акыркы 8 элементин көрсөк, экинчи массивде ушундай эле маанидеги элемент бар. Ошентип, 8 жооп болуп саналбайт. Ошентип, жооп биринчи массивдин алгачкы 2 элементинен улам 2ге барабар болот.

Leitcode Solution эки массивдин ортосундагы аралыкты табуу үчүн орой мамиле ыкмасы

Маселе үчүн орой күч чечими уникалдуу жуптарды тандап алган эки массивдин үстүнөн кайталанат. Андан кийин бул уникалдуу түгөйлөрдүн ортосундагы айырма берилген 'd' бүтүн санынан аз болсо текшерилет. Эгер айырмачылык d-ден аз болсо, анда элементти желекчеге илебиз. Белгиленген элементтерди эсептебейбиз жана калган элементтердин саны жооп катары кайтарылып берилет. Чечим алдыга карай түз, бирок андан да жакшы чечим болушу мүмкүн.

Leitcode Solution эки массивдин ортосундагы аралыкты табуу үчүн оптималдаштырылган ыкма

Жогорудагы ыкма боюнча, биз эки уя курулган циклди колдондук. Бирок, акырында, биз биринчи массивдеги учурдагы элементтин экинчи массивдеги айырмасы d ден аз болгон бир эле элемент бар экендигин текшеришибиз керек болчу. Ошентип, биринчи массивден тандалган элементке жакын эки элементти тандап алсак. Эгерде ушул эки жакын элементтин минималдуу абсолюттук айырмасы d ден ашпаса, анда башка эч бир элемент жакшы натыйжа бере албайт деп толук айта алабыз.

Ошентип, маселе биринчи массивдин тандалган элементине жакын эки элементти табууга чейин жетет (экинчи массивден). Бул эки жакын элементти табуу үчүн, экинчи массивди иреттеп, экилик издөөнү колдонобуз. Экилик издөөнү колдонуп, тандалган элементтен бирдей же чоң элемент табабыз. Учурдагы элементтен кичинекей эле элемент айырманы баалоо үчүн колдонулат.

Эгерде бул айырмачылыктар 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

Комплекстик анализ

Убакыт татаалдыгы

O (max (M, N) logN), анткени биз экинчи массивди иреттеп, биринчи массивдеги ар бир элемент боюнча экилик издөөнү жүргүзөбүз. Бул жерде M, N - тиешелүүлүгүнө жараша биринчи жана экинчи массивдеги элементтердин саны.

Космостун татаалдыгы

O (N), экинчи массивди иреттөө үчүн бош орун.