找到数组中的最大差异对

Question

我正在研究一些kata,但我无法通过所有测试用例.

所以情况是:

给定任何数组,例如此数组:int[] a = {2, 3, 10, 2, 4, 8, 1},找到数组中的最大差异对,同时确保较大的值处于较高的索引而不是较低的值.

在这个例子中:10是最大的元素,1是最小的元素,因为10它在索引处2,1在索引处6,因此它不计数,因为较大的对在较低的索引处.因此,正确的答案是a[0],和a[2],最大的不同是10-2.

其他要求是数组大小N介于1和之间1_000_000,任何给定a[i]的介于-1_000_000和之间1_000_000

我写了这样的代码:

static int maxDifference(int[] a) {
    //test array size
    if (a.length < 1 || a.length > 1_000_000) return -1;

    int[] oldArr = Arrays.copyOf(a, a.length);
    Arrays.sort(a);
    int max = a[a.length - 1];
    if (max > 1_000_000 || a[0] < -1_000_000) return -1;

    int min = max;
    for (int i = 0; i < oldArr.length; i++) {
        if (oldArr[i] < max) {
            min = Math.min(min, oldArr[i]);
        }
        if (oldArr[i] == max) break;
    }
    int result = min == max ? -1 : max - min;
    return result;
}

我的逻辑几乎是制作数组的副本然后对数组进行排序,然后循环它,保留指向最大值和最小值的指针,然后得到结果.

令我感到不安的是我只知道有一些我没有通过的测试用例,但没有提示为什么它没有通过.任何人都可以给我一些建议,以及我在这个辅助方法中可能缺少什么？

Answer 1

基本上你需要跟踪到目前为止找到的最小值和到目前为止找到的最大差异:

static int maxDifference(int[] a) {
    int minimum, diff = -1;
    if(a.length == 0) {
        return -1;
    }
    minimum = a[0];
    for (int i = 1; i < a.length; i++) {
        diff = Math.max(diff, a[i] - minimum);
        minimum = Math.min(minimum, a[i]);
    }
    return diff;
    // depending on interpretation of requirements, above line might be wrong
    // Instead, use:
    // return diff > 0 ? diff : -1;
}

Answer 2

如果性能不是问题（我认为，因为您正在对数组进行排序，这可能不是最有效的实现），那么这段简单但易于阅读的代码应该可以解决问题：

public static int maxDifference(int[] a) {
    long bounds = 1_000_000;

    int biggestDifference = -1;
    if (a.length > bounds) {
        return -1;
    }
    for (int i = 0; i < a.length-1; i++) {
        if (Math.abs(a[i]) > bounds) {
            return -1;
        }
        for (int j = i+1; j < a.length; j++) {
            int difference = Math.abs(a[j] - a[i]);
            if (difference > biggestDifference) {
                biggestDifference = difference;
            }
        }
    }
    return biggestDifference;
}