2

Есть два массива. Необходимо получить минимальную разницу между элементами первого и второго массивов. Например [ 1, 4, 8, 12] и [5, 6, 13, 19]. Ответ должен быть 1, разница между 4 и 5. Понимаю, что нужно массивы смержить и взять минимальную разницу между двумя элементами в массиве, но как объединить так, чтобы понимать с какого массива это число?

5
  • Можно и не мержить, а "в лоб" решать: каждое первого массива с каждым второго проверять. 23 окт 2017 в 9:09
  • Если ответ должен быть 1, то зачем знать с какого массива число?
    – tilin
    23 окт 2017 в 9:09
  • @tilin потому что должна смотреться разница именно между числами между двумя массивами, а так представь, что 4 и 5 будет в первом массиве. Ответ будет неверным 23 окт 2017 в 9:14
  • Не вижу причин не делать два цикла со сравнением 23 окт 2017 в 9:20
  • 1) Сортируешь массивы, если они ещё не сортированные. 2) Сливаешь (merge) оба массива как при сортировке слияния, при этом когда сливаешь то тебе ведь известно где элемент первого массива где второго, так вот сливаешь и при слиянии просто сразу сохраняешь минммум между двумя массивами, при этом сам слитый массив не нужен потому можно такой массив даже не делать, т.е. сравнение слиянием достаточно делать.
    – Arty
    23 окт 2017 в 9:47

4 ответа 4

0

Так как вам нужно получить минимальную разницу между каждыми элементами массивов, то можно так:

  1. создаем новый массив элементы в котором - это разницы каждого элемента одного массива с каждым элементом второго массива
  2. сортируем полученный массив по возрастанию
  3. берем у отсортированного массива нулевой элемент

Array.prototype.allDiff = function(a){
    return this.reduce((p,c) => {
      a.forEach(e => {
        p.push(Math.abs(e-c));
      });
      return p;
    }, []);
};

console.log([1, 4, 8, 21].allDiff([5, 6, 13, 19]).sort((a,b) => a-b)[0]);

UPD: предыдущий код, конечно, совсем не оптимален с точки зрения производительности. Немного улучшить ситуацию, если не нужно сохранять все разницы, можно убрав формирование выходного массива и сразу вычислять минимум

Array.prototype.allDiff = function(a){
    return this.reduce((p,c) => {
      a.forEach(e => {
        if(p === undefined){
          p = Math.abs(e-c);
        }else{
          p = Math.min(p, Math.abs(e-c));
        }
      });
      return p;
    }, undefined);
};

console.log([1, 4, 8, 21].allDiff([5, 6, 13, 19]));

4
  • спасибо большое, отличный код, решил сам, но воспользуюсь вашим 23 окт 2017 в 9:58
  • @takecaretakecaretakecare в итоге в этом решении используется 3 цикла, тогда как решение "в лоб" - только 2 23 окт 2017 в 10:17
  • Можно значительно упростить, если мы уже каждый с каждым сравниваем, когда формируем массив новый, тогда зачем нам во первых сохранять этот результирующий массив, а во вторых зачем его сортировать - нам же нужно найти минимум в этом массиве, тогда мы просто когда каждый с каждым сравниваем то просто сразу же и выбираем минимум из величин разницы каждого с каждым. Сортировка же будет делаться дополнительное O(N * log(N)) время.
    – Arty
    23 окт 2017 в 10:18
  • конечно сортировка не требуется. выходной массив был просто для удобства понимания. Добавил вариант без сортировки.
    – tilin
    23 окт 2017 в 10:37
0

Предлагаю Вам такой код. Он вероятно не производительный. Алгоритм: перебор "втупую". Можно конечно было обратить внимание, что в вопросе вы указали отсортированные массивы, и упростить алгоритм за счёт break; (с доп. условием) в первом вложенном цикле for() по j внутри метода find(), но мне очень лень :)
Программа, которую я дал (прошу заметить: на Java!), показывает между какими элементами двух массивов нашлась наименьшая разница (по модулю), и показывает саму разницу.

Действующие лица:
print(int[] a, int i) -- красиво печатает массив, указывая галочкой на i-ый элемент
delta(int a, int b) = |a-b|
find(int[] a1, int[] a2) -- главное действующее лицо, которое собственно выполняет поиск наименьшей разницы выводя нам аккуратно массивы с указанием на образующие наименьшую разность элементы; так же данный метод вывод и саму дельту.

package test;

public class Main {
    static void print(int[] a, int index) {
        for (int i = 0; i < a.length - 1; i++)
            System.out.print(a[i] + ", ");
        System.out.println(a[a.length - 1]);
        for (int i = 0; i < a.length; i++) {
            int k = 1, t = a[i];
            if (t>=0) {} else {t=-t; k++;}
            while ((t = t / 10) > 0)
                k++;
            StringBuilder sb = new StringBuilder("");
            while (k-- > 0)
                sb.append(" ");
            String s = sb.toString();
            System.out.print(i == index ? "^" + s + " " : s + "  ");

        }
        System.out.println();
    }

    static int delta(int x1, int x2) {
        return Math.abs(x1 - x2);
    }

    static void find(int[] a1, int[] a2) {
        int[] min = new int[3];
        min[0] = delta(a1[0], a2[a2.length - 1]) > delta(a1[a1.length - 1], a2[0]) ? delta(a1[0], a2[a2.length - 1])
                : delta(a1[a1.length - 1], a2[0]);
        for (int i = 0; i < a1.length; i++)
            for (int j = 0; j < a2.length; j++)
                if (delta(a1[i], a2[j]) <= min[0]) {
                    min[0] = delta(a1[i], a2[j]);
                    min[1] = i;
                    min[2] = j;
                }
        print(a1,min[1]);
        print(a2,min[2]);
        System.out.println("\n");
        System.out.println("Result delta = "+min[0]);
    }

    public static void main(String[] args) {
        int[] a1 = { 1, 4, 8, 12, 18, 328, 99482}, a2 = {35, -27, 325, 9482};
        find(a1, a2);
    }
}

out:
1, 4, 8, 12, 18, 328, 99482
                 ^           
35, -27, 325, 9482
         ^          


Result delta = 3
0
    function compare(arr1, arr2) {
let min = Math.abs(arr1[0] - arr2[0]);
  let i=0; let j=0;
  while(i < arr1.length && j < arr2.length) {

    let x = arr1[i] - arr2[j];
    if (x < 0) {
        x = -x;
        i++;
   }
    else if (x > 0) {
    j++;
   }
    else {
    return 0;
   }
    if (x < min) {
    min = x;
   }
  }
  return min;
}

мое корявое решение, всем спасибо за ответ

0

Зависит от того какие объёмы данных и как быстро должен алгоритм отрабатывать, если объёмы не большие то можно использовать простейший алгоритм с квадратичной сложностью - сравнить в двойном цикле каждый элемент первого массива с каждым вторым и сохранить минимальную разницу.

Но если нужен быстрый алгоритм тогда предлагаю такой - вначале сортируем оба массива по возрастанию, потом поступаем также как в сортировке слиянием, т.е. сравниваем сливаемые рубежи массивов и сохраняем минмум из разницы внутри пары элементов, при этом результирующий слитый массив нам не нужен. Сложность алгоритма O(N*log(N)) для сортировки плюс O(N) для слияния.

Т.к. не знаю толком JavaScript, вот написал код на C++ для последнего алгоритма, понять его не сложно и можно адаптировать для JavaScript, также можно запустить алгоритм онлайн:

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
#include <cstdlib>
using namespace std;

int main() {
    vector<int> a = {1, 4, 8, 12}, b = {5, 6, 13, 19};
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    size_t pa = 0, pb = 0;
    int min_diff = numeric_limits<int>::max();
    while (pa < a.size() && pb < b.size()) {
        min_diff = min(min_diff, abs(a[pa] - b[pb]));
        if (a[pa] < b[pb]) ++pa; else ++pb;
    }
    cout << min_diff << endl;
    return 0;
}

Вот изучил немного JavaScript и написал ещё решение для первого алгоритма с квадратичной сложностью, можно запустить онлайн:

function MinDiff(a, b) {
  var min_diff = Math.abs(a[0] - b[0]);
  for (var i = 0; i < a.length; ++i) {
    for (var j = 0; j < b.length; ++j) {
      min_diff = Math.min(min_diff, Math.abs(a[i] - b[j]));
    }
  }
  return min_diff;
}

console.log(MinDiff([1, 4, 8, 21], [5, 6, 13, 19]))

Вот ещё C++ алгоритм который быстрый переписал на JavaScript, запустить онлайн:

function MinDiff2(a, b) {
  a.sort((a,b)=>a-b);
  b.sort((a,b)=>a-b);
  var min_diff = Math.abs(a[0] - b[0]);
  var pa = 0, pb = 0;
  while (pa < a.length && pb < b.length) {
    min_diff = Math.min(min_diff, Math.abs(a[pa] - b[pb]));
    if (a[pa] < b[pb]) ++pa; else ++pb;
  }
  return min_diff;
}

console.log(MinDiff2([1, 4, 8, 21], [5, 6, 13, 19]))

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.