Как найти ближайшие числа из массива?

Question

[we1]

Дан массив из N чисел. Нужно найти от двух до N-1 ближайших друг к другу числе. Хотя бы два найти, уже будет хорошо.
То есть нужно не минимальные, не максимальные, не средние, а именно два числа, которые ближе друг к другу.
Например в массиве -22, -20, -4, -4.6, -1, 0, 0.3, 19.9, 20, 21 ближайшими окажутся 19.9 и 20.
Кажется слишком сложным для каждого числа создавать свой массив с разностью его и остальных чисел, потом искать в этих массивах минимальное значение и сортировать потом эти результаты из разных массивов. Должен же быть вариант попроще?

Answer 1

[Mikhail Osher]

Не покидает ощущение, что такую задачу на Codewars решал.

function findPair(input) {
  let minDiff = Infinity;
  let index = 0;

  for (let i = 0; i < input.length - 1; i++) {
    const cur = input[i];
    const next = input[i + 1];
    const diff = Math.abs(cur - next);

    if (diff < minDiff) {
      minDiff = diff;
      index = i;
    }
  }

  return input.slice(index, index + 2);
}

console.log(findPair([-22, -20, -4, -4.6, -1, 0, 0.3, 19.9, 20, 21]));

Comments

[we1]

Вроде похоже на решение. Только вот про абсолютное значение сомневаюсь. Мне кажется, что лучше прибавить ко всем числам что-то заведомо большое, чтобы все числа были положительными.
Что-то не соображу, что получится при -22 - (-20). -2 или -42 ? Я правда не догоняю, получается, что арифметику забыл уже.

[Mikhail Osher]

we1, вроде похоже? Возвращает [19.9, 20]

[we1]

Mikhail Osher, как бы да)) Должно получаться правильно. Кажется, что надо предварительно отсортировать массив?

Answer 2

[Denis]

Можно сделать на основе kNN, вычисляем ближайших соседей для каждого числа в массиве, а дальше уже работаем с массивами соседей.
Такой подход будет работать и на не отсортированном массиве.

Comments

[we1]

Ближайшие соседи — это значит для каждого числа надо прогнать массив и найти одно число минимально больше и одно минимально меньше? А дальше как?

[Denis]

Нет. просто для каждого элемента массива строится такой массив размера "K", где с увеличением индекса растет модуль разности. т.е. чем больше индекс тем больше расстояние от исходного элемента.