递归查找数组中差异最小的两个元素

Question

我正在尝试以递归方式查找数组中差异最小的两个元素（假设数组已经按升序排序）。

我一直在努力让我的代码达到 return 最小的总和，但递归似乎有问题。

public class SmallestDiff {
    public static void main (String [] args){
        int [] x = {1,3,6,9,126};
        System.out.println(smallestDiff(x,4));
    }

    public static int smallestDiff (int [] array, int index){
        int result;
        if (index>0){
            int diff = Math.abs((array[index]-array[index-1]));
            result = Math.min (diff, smallestDiff(array,index-1));
        }
        else {
            return array[0];
        }
        return result;
    }
}

Answer 1

你的错误是

return array[0];

array[0] 不是值之间的差异，因此不应返回。修复程序的最简单方法是将此行替换为

return array[1] - array[0];

Answer 2

试试这个：

public class 最小差异 {

public static void main(String[] args) {
    int[] x = { 1, 3, 6, 9, 126 };

    int result;
    if (x.length < 2) {
        result = x[0];
    }
    else{
        result = smallestDiff(x, x.length-1);
    }
    System.out.println(result);

}

public static int smallestDiff(int[] array, int index) {

    if (index == 0) {
        return Integer.MAX_VALUE;

    }

    int diff = (array[index] - array[index - 1]);
    return Math.min(diff, smallestDiff(array, index - 1));

}

}

如果数组中只有一个元素，此解决方案将打印第一个元素。否则，它总是导致两个元素之间的最小差异。

Answer 3

如果您的数组已排序，则无需递归。下面的代码通过迭代解决了这个问题。

public class SmallestDiff {

public static void main(String[] args) {
    int[] x = {1, 3, 6, 9, 126};
    System.out.println(smallestDiff(x));
}

public static int smallestDiff(int[] array) {
    int result = Integer.MAX_VALUE;
    for (int i = 0; i < array.length - 1; i++) {
        int diff = Math.abs((array[i] - array[i + 1]));
        if (diff < result) {
            result = diff;
        }
    }
    return result;
}

}

递归查找数组中差异最小的两个元素

recursively finding two elements with the smallest difference in an array

java

arrays

algorithm

recursion

difference