求数组中的最小绝对差

题目描述

绝对差：可以理解为数轴上两个点之间的距离。

给定一个整数数组，返回一个新数组，包含绝对差值为最小的数值对。

Example1: 最小绝对差值是 1，因为返回所有绝对差[ [1, 2], [2, 3], [3, 4]]。

Input: [4, 2, 1, 3]
Output: [ [1, 2], [2, 3], [3, 4]]

Example2: 最小绝对差值是 2，因此返回 [[1, 3]]。

Input: [1, 3, 6, 10, 15]
Output: [[1, 3]]

Input: [3, 8, -10, 23, 19, -4, -14, 27]
Output: [[-14, -10],[19, 23],[23, 27]]

Code

时间复杂度：O(NLogN) 取决于 JavaScript 内置的 sort 方法的时间复杂度。

function minimumAbsDifference(arr) {
  arr.sort((a, b) => a - b);
  let best = Math.abs(arr[0] - arr[1]);
  let result = [[arr[0], arr[1]]];
  for (let i = 1; i < arr.length - 1; i++) {
    let diff = Math.abs(arr[i] - arr[i + 1]);
    if (diff < best) {
      result = [];
      best = diff;
      result.push([arr[i], arr[i + 1]]);
    } else if (diff === best) {
      result.push([arr[i], arr[i + 1]]);
    }
  }
  return result;
}

Test Cases

const {
  minimumAbsDifference,
} = require('../docs/algo/array/minimumAbsDifference');

describe('minimumAbsDifference', () => {
  it('case 1', () => {
    expect(minimumAbsDifference([4, 2, 1, 3])).toEqual([
      [1, 2],
      [2, 3],
      [3, 4],
    ]);
  });
  it('case 2', () => {
    expect(minimumAbsDifference([1, 3, 6, 10, 15])).toEqual([[1, 3]]);
  });
  it('case 3', () => {
    expect(minimumAbsDifference([3, 8, -10, 23, 19, -4, -14, 27])).toEqual([
      [-14, -10],
      [19, 23],
      [23, 27],
    ]);
  });
});