30

我有一个具有有限数量值的整数数组。我的工作是找出数组中任意两个元素之间的最小差异。

考虑数组包含

4, 9, 1, 32, 13

这里的差异是 4 和 1 之间的最小值，所以答案是 3。

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

4

8 回答 8

47

最小差异将是排序顺序中连续对之间的差异之一。对数组进行排序，并通过相邻数字对寻找最小的差异：

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。

于 2012-09-02T02:17:03.917 回答
13

您可以利用您正在考虑整数来制作线性算法的事实：

  1. 第一遍：计算最大值和最小值
  2. 第二遍：分配一个长度为 (max - min + 1) 的布尔数组，初始化为 false，并将数组中的每个值的第 (value - min)th 值更改为 true
  3. 第三遍：计算布尔数组的真值条目的索引之间的差异。
于 2014-08-08T22:18:16.457 回答
7

虽然所有答案都是正确的，但我想展示负责n log n运行时的底层算法。找到两点之间的最小距离或在一维平面中找到最近点的分而治之的方法。

通用算法：

在此处输入图像描述

  • 设 m = 中位数 (S)。
  • 在 m 处将 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}`);

于 2017-03-28T12:43:52.037 回答
4

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

于 2012-09-02T05:35:11.447 回答
4

这实际上是对closest-pair问题的重述one-dimension。 https://en.wikipedia.org/wiki/Closest_pair_of_points_problem http://www.cs.umd.edu/~samir/grant/cp.pdf

正如下面引用的维基百科文章所指出的，这个问题的最佳决策树模型也能Ω(nlogn)及时运行。

于 2015-06-18T18:18:21.907 回答
2

分享最简单的解决方案。

function FindMin(arr) {

    //sort the array in increasing order

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

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

    let n = arr.length;

    for (var i=0;i<n;i++) {

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

    return m; // minimum difference.
  }
于 2019-10-19T13:02:39.537 回答
1

给定的问题可以在 O(n) 时间内轻松解决。看下面我写的代码。

    import java.util.Scanner;
    public class Solution {
    public static void main(String [] args) {
        Scanner input = new Scanner(System.in);
        int i, minDistance = 999999;
        boolean flag = false;
        int capacity = input.nextInt();
        int arr[] = new int[capacity];
        for (i = 0; i < capacity; i++) {
            arr[i] = input.nextInt();
        }

        int firstElement = input.nextInt();
        int secondElement = input.nextInt();

        int prev = 0;

        for (i = 0; i < capacity; i++) {
            if (arr[i] == firstElement || arr[i] == secondElement) {
                prev = i;
                break;
            }
        }

        for (; i < capacity; i++) {
            if(arr[i] == firstElement || arr[i] == secondElement) {
                if(arr[i] != arr[prev] && minDistance > Math.abs(i - prev)) {
                    minDistance = Math.abs(i - prev);
                    flag = true;
                    prev = i;
                } else {
                    prev = i;
                }
            }
        }

        if(flag)
            System.out.println(minDistance);
        else
            System.out.println("-1");
    }
}
于 2020-02-24T19:08:02.600 回答
-1

在 Python 3 中，这个问题可以通过使用模块itertools来简化，它提供了可用于列表的组合。从该列表中，我们可以找到每个组合的总和并找到这些值的最小值。

import itertools

arr = [4, 9, 1, 32, 13]

if len(arr) > 1:
    min_diff = abs(arr[0] - arr[1])
else:
    min_diff = 0

for n1, n2 in itertools.combinations(arr, 2): # Get the combinations of numbers
    diff = abs(n1-n2) # Find the absolute difference of each combination
    if min_diff > diff:
        min_diff = diff # Replace incase a least differnce found

print(min_diff)
于 2019-11-26T17:43:58.690 回答