查找数组中的最大差异对

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

如果性能是不是一个问题（我假设，因为你排数组这可能不是最有效的实现），这简单但容易可读的代码应该做的伎俩：

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

Answer 2

基本上你需要保持迄今为止发现的最小值和最大值差异迄今发现的轨道：

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 3

此找到当地的最小值和最大值，并跟踪了全球最小的和的位置C urrent最大差异。

import java.util.Arrays; 

public class MaxDifference { 
    private static long difference(
      final int[] array, 
      final int minPos, 
      final int maxPos 
    ) 
    { 
     assert(minPos < maxPos); 
     assert(array[minPos] < array[maxPos]); 
     return ((long) array[maxPos]) - ((long) array[minPos]); 
    } 

    public static int[] maxDifference(final int[] array){ 
     if (array == null|| array.length < 2) 
      return null; 

     // Position of global minima. 
     int minimaPos     = 0; 
     // Value of global minima. 
     int minimaValue    = array[0]; 
     // Position of minima for current maximum difference. 
     int minimaPosForMaxDifference = 0; 
     // Position of maxima for current maximum difference. 
     int maximaPosForMaxDifference = -1; 
     // Current maximum difference. 
     long maxDifference   = -1; 
     // Current position 
     int pos      = 0; 


     while (pos < array.length - 1){ 
      // Find the local minima 
      while(pos < array.length - 1 && array[pos] > array[pos + 1]) 
      { 
       pos++; 
      } 
      // Test if the local minima is the current global minima. 
      if (array[pos] < minimaValue) 
      { 
       minimaPos = pos; 
       minimaValue = array[pos]; 
      } 

      // Find the local maxima 
      while(pos < array.length - 1 && array[pos] <= array[pos + 1]) 
      { 
       pos++; 
      } 

      if (pos > minimaPos) 
      { 
       long diff = difference(array, minimaPos, pos); 
       if (diff > maxDifference) 
       { 
        minimaPosForMaxDifference = minimaPos; 
        maximaPosForMaxDifference = pos; 
        maxDifference = diff; 
       } 
      } 

     } 
     if (maximaPosForMaxDifference == -1) 
      return null; 

     return new int[]{ minimaPosForMaxDifference, maximaPosForMaxDifference }; 
    } 

    public static String toDiffString(final int[] array){ 
     final int[] diff = maxDifference(array); 
     if (diff == null) 
      return String.format(
        "%s has no maximum difference", 
        Arrays.toString(array) 
      ); 
     else 
      return String.format(
        "%s has maximum difference of %d at %s", 
        Arrays.toString(array), 
        difference(array, diff[0], diff[1]), 
        Arrays.toString(diff) 
      ); 
    } 
    public static void main(final String[] args){ 
     System.out.println(toDiffString(new int[]{})); 
     System.out.println(toDiffString(new int[]{ 0 })); 
     System.out.println(toDiffString(new int[]{ 0, 0 })); 
     System.out.println(toDiffString(new int[]{ 1, 0 })); 
     System.out.println(toDiffString(new int[]{ 2, 1, 0 })); 
     System.out.println(toDiffString(new int[]{ 0, 1, 2 })); 
     System.out.println(toDiffString(new int[]{2, 3, 10, 2, 4, 8, 1})); 
     System.out.println(toDiffString(new int[]{5,0,3,1,4})); 
     System.out.println(toDiffString(new int[]{5,0,3,-1,4})); 
     System.out.println(toDiffString(new int[]{ Integer.MIN_VALUE, Integer.MAX_VALUE })); 
    } 
} 

输出：

[] has no maximum difference 
[0] has no maximum difference 
[0, 0] has maximum difference of 0 at [0, 1] 
[1, 0] has no maximum difference 
[2, 1, 0] has no maximum difference 
[0, 1, 2] has maximum difference of 2 at [0, 2] 
[2, 3, 10, 2, 4, 8, 1] has maximum difference of 8 at [0, 2] 
[5, 0, 3, 1, 4] has maximum difference of 4 at [1, 4] 
[5, 0, 3, -1, 4] has maximum difference of 5 at [3, 4] 
[-2147483648, 2147483647] has maximum difference of 4294967295 at [0, 1] 

Answer 4

只是要注意的是阿米特的解决方案的工作要么最小或最大的工作。使用最大值的好的属性是，你只需要一个额外的功能（Math.Max）。对于不信者，只需进行单元测试并检查。无论如何，这在O（n）中确实可以解决。

//using minimum (Amit's solution - vote him up!) 
static int maxDifferenceWithMin(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; 
} 

//using maximum 
static int maxDifferenceWithMax(int[] a) { 
    int maximum, diff = -1; 
    if(a.length == 0) { 
     return -1; 
    } 
    maximum = a[a.length - 1]; 
    for (int i = a.length - 1; i >= 0; i--) { 
     diff = Math.max(diff, a[i] - maximum); 
     maximum = Math.max(maximum, a[i]); 
    } 
    return diff; 
}