查找數組中的最大差異對

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; 
}