在 Node.JS 中找到 A 和 B 之间的最短距离

Question

这是解决此问题的最佳和最快的方法：

求A和B之间的最短距离，A和B在一个数组中，数组中有值的列表，例如[4, 8, 9, 10, 100]，我们需要找出最小的该数组中两个值之间的差距。如果它是负数，则使用绝对值。

Answer 1

如果先对数组进行排序，就可以找到任意两个相邻元素之间的绝对值差值最小的那个。

let data = [4,8,9,10,100];

function findSmallDelta(data) {

  data.sort();
  let minDelta = -1;
  for (let i = 0; i < data.length - 1; i++) {
      let delta = Math.abs(data[i] - data[i+1]);
      if (minDelta === -1 || delta < minDelta) {
          minDelta = delta;
      }
  }
  return minDelta;
}

console.log(findSmallDelta(data));

如果不想影响源数组，可以在排序前复制源数组。似乎对数组进行排序然后仅测试相邻元素之间的增量可能比比较所有可能的增量更快。

Answer 2

给定数组排序
找到排序数组中一对元素的最小差异
找出所有差异最小的对

function closetPairs (arr) {
    let result = []; 
    let minDiff = Number.MAX_VALUE;

    arr.sort((a, b) => { 
        return a - b;
    });

    // find the lowest difference for a pair of elements in the sorted array
    for (let i = 0; i < arr.length - 1; i++) {
        let currDiff = arr[i + 1] - arr[i];
        if (currDiff < minDiff) {
            minDiff = currDiff;
        }
    }

    // find all the pairs with lowest differnece
        for (let j = 0; j < arr.length - 1; j++) {
            let sortedEleDiff = arr[j + 1] - arr[j];
            if (minDiff == sortedEleDiff) {
                result.push(arr[j + 1], arr[j]);
            }
        }

        return result.sort((a, b) => { 
            return a - b;
        });

    }

    let inputArr = [4, 8, 9, 10, 100];

    console.log(closetPairs(inputArr)); // [ 8, 9, 9, 10 ]

在 Node.JS 中找到 A 和 B 之间的最短距离

Find the shortest distance between A and B in Node.JS

shortest-path

node.js