找出数组中元素之间的最小差异

Question

我有一个整数数组,其值有限.我的工作是找到数组中任何两个元素之间的最小差异.

考虑一下该数组包含

4, 9, 1, 32, 13

这里差异最小在4到1之间,所以答案是3.

什么应该是解决这个问题的算法.另外,我不知道为什么但我觉得使用树木,这个问题可以解决相对容易.可以这样做吗？

Answer 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.

Answer 2

您可以利用以下事实:您正在考虑使用整数来生成线性算法:

1. 第一遍:计算最大值和最小值
2. 第二遍:分配一个长度为布尔数组(max - min + 1),false初始化,并为数组中的每个值将(value - min)th值更改为true
3. 第三遍:计算布尔数组的真值项的索引之间的差异.

Answer 3

虽然所有答案都是正确的,但我想展示负责n log n运行时的基础算法.的分而治之发现两点之间的最小距离或在1-d平面查找最近点的方式.

一般算法:

• 设m =中位数(S).
• 将S分为S1,S2为m.
• δ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}`);

Answer 4

我会将它们放入堆中，O(nlogn)然后逐个弹出，并获得我弹出的每个元素之间的最小差异。最后我会得到最小的差异。然而，可能有更好的解决方案。