Выяснение минимальной разницы между элементами массива

У меня есть целочисленный массив с некоторым конечным числом значений. Моя задача - найти минимальную разницу между любыми двумя элементами в массиве.

Учтите, что массив содержит

4, 9, 1, 32, 13

Здесь разница минимальна между 4 и 1, поэтому ответ равен 3.

Каким должен быть алгоритм для решения этой проблемы. Кроме того, я не знаю, почему, но я чувствую, что используя деревья, эта проблема может быть решена относительно проще. Это можно сделать?

Ответы

Ответ 1

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

int[] a = new int[] {4, 9, 1, 32, 13};
Arrays.sort(a);
int minDiff = a[1]-a[0];
for (int i = 2 ; i != a.length ; i++) {
    minDiff = Math.min(minDiff, a[i]-a[i-1]);
}
System.out.println(minDiff);

Отпечатает 3.

Ответ 2

Вы можете воспользоваться тем, что вы рассматриваете целые числа для создания линейного алгоритма:

  • Первый проход: вычислить максимум и минимум
  • Второй проход: выделяет логический массив длины (max - min + 1), ложный инициализированный, и измените значение (value-min) th на true для каждого значения в массиве
  • Третий проход: вычислить различия между индексами истиннозначных записей булевого массива.

Ответ 3

Хотя все ответы верны, я хотел показать основной алгоритм, отвечающий за время выполнения n log n. Разделяй и властвуй способ нахождения минимального расстояния между двумя точками или нахождения ближайших точек в 1-D плоскости.

Общий алгоритм:

enter image description here

  • Пусть m = медиана (S).
  • Разделите S на S1, S2 на м.
  • δ1 = ближайшая пара (S1).
  • δ2 = Ближайшая пара (S2).
  • δ12 - минимальное расстояние по разрезу.
  • Вернуть δ = min (δ1, δ2, δ12).

Вот пример, который я создал в Javascript:

// Points in 1-D
var points = [4, 9, 1, 32, 13];

var smallestDiff;

function mergeSort(arr) {
  if (arr.length == 1)
    return arr;

  if (arr.length > 1) {
    let breakpoint = Math.ceil((arr.length / 2));
    // Left list starts with 0, breakpoint-1
    let leftList = arr.slice(0, breakpoint);
    // Right list starts with breakpoint, length-1
    let rightList = arr.slice(breakpoint, arr.length);

    // Make a recursive call
    leftList = mergeSort(leftList);
    rightList = mergeSort(rightList);

    var a = merge(leftList, rightList);
    return a;
  }
}

function merge(leftList, rightList) {
  let result = [];
  while (leftList.length && rightList.length) {
    // Sorting the x coordinates
    if (leftList[0] <= rightList[0]) {
      result.push(leftList.shift());
    } else {
      result.push(rightList.shift());
    }
  }

  while (leftList.length)
    result.push(leftList.shift());

  while (rightList.length)
    result.push(rightList.shift());

  let diff;
  if (result.length > 1) {
    diff = result[1] - result[0];
  } else {
    diff = result[0];
  }

  if (smallestDiff) {
    if (diff < smallestDiff)
      smallestDiff = diff;
  } else {
    smallestDiff = diff;
  }
  return result;
}

mergeSort(points);

console.log('Smallest difference: ${smallestDiff}');

Ответ 4

Я бы поместил их в кучу в O(nlogn), а затем пошатнул один за другим и получал минимальную разницу между каждым элементом, который я pop. Наконец, у меня была бы минимальная разница. Однако может быть лучшее решение.

Ответ 6

поделиться самым простым решением.

function FindMin (arr) {

//сортируем массив в порядке возрастания

arr.sort((a, b) => {    вернуть а-б; });

let min = arr [1] -arr [0];

let n = arr.length;

для (var i = 0; i 

let m = arr[i+1] - arr[i];
if(m < min){
  m = min;
}

}

возврат м;//минимальная разница.

}