使用子集 - 成對差異（數組）

Question

我正在嘗試編寫一個程序，該程序需要一個數組，有效地對數組viaquickSort進行排序，然後對於排序數組中的每對具有通過整數參數傳遞的指定差異方法中的參數），它根據指定的差值輸出對。該方法有效地返回一個ArrayList與不同的整數對。例如。讓我們假設我有一個數組，就像{16，12，7，8，4，13，9，20}。如果通過的整數是4，它將返回的對是

（4,8）（8,12）（9,13）（12,16）（16,20）

出於某種原因，不過，我的代碼不這樣做，我得到一個運行時錯誤：

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space 
at java.util.Arrays.copyOf(Arrays.java:3210) 
at java.util.Arrays.copyOf(Arrays.java:3181) 
at java.util.ArrayList.grow(ArrayList.java:261) 
at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235) 
at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227) 
at java.util.ArrayList.add(ArrayList.java:458) 
at DifferencePairs.findPairs(DifferencePairs.java:20) 
at DifferencePairs.main(DifferencePairs.java:72) 

這裏是我的代碼，我做了什麼：

import java.util.ArrayList; 

public class DifferencePairs { 
    public static ArrayList<Pair> findPairs(int[] array, int diff) { 
     /* 
     * sort the array. This takes O(n log n) (quicksort) 
Then for each x in array A, use binary search to look for difference in elements. This will take O(logn). 
So, overall search is O(n log n) 
     */ 
     sort(array); 
     int i = 0; 
     int j = 1; 
     int sizeOfArray = array.length; 

     ArrayList<Pair> differencePairs = new ArrayList <Pair>(); 
     while (i < sizeOfArray && j < sizeOfArray) { 
      if (i != j && (array[j] - array[i] == diff)) { 

       Pair newPair = new Pair(array[j], array[i]); 
       differencePairs.add(newPair); 
      } else if (array[j] - array[i] < diff) { 
       j++; 
      } else if (array[j] - array[i] > diff){ 
       i++; 

      } 
     } return differencePairs;    
    } 


    public static void sort(int[] arr) 
    { 
     quickSort(arr, 0, arr.length - 1); 
    } 
    /** Quick sort function **/ 
    public static void quickSort(int arr[], int low, int high) 
    { 
     int i = low, j = high; 
     int temp; 
     int pivot = arr[(low + high)/2]; 

     /** partition **/ 
     while (i <= j) 
     { 
      while (arr[i] < pivot) 
       i++; 
      while (arr[j] > pivot) 
       j--; 
      if (i <= j) 
      { 
       /** swap **/ 
       temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 

       i++; 
       j--; 
      } 
     } 

     /** recursively sort lower half **/ 
     if (low < j) 
      quickSort(arr, low, j); 
     /** recursively sort upper half **/ 
     if (i < high) 
      quickSort(arr, i, high); 
    } 

    public static void main(String[] args) { 
     int[] myArray = {16, 12, 7, 8, 4, 13, 9, 20}; 
     ArrayList<Pair> pairs = findPairs(myArray, 4); 
     for (Pair pair: pairs) { 
      System.out.println(pair.toString()); 
     } 
    }    
} 

和如果你想知道下一個Class是Pair類。請告訴我我哪裏出錯了。謝謝！

public class Pair { 

    private int first; 
    private int last; 

    public Pair(int first, int last) 
    { 
     this.first = first; 
     this.last= last; 

    } 
    public int getFirst() { 
     return first; 
    } 

    public void setFirst(int first) { 
     this.first = first; 
    } 

    public int getLast() { 
     return last; 
    } 

    public void setLast(int last) { 
     this.last = last; 
    } 

    public String toString() 
    { 
     return "(" + this.first + " , " + this.last+ ")"; 
    } 


} 

Answer 1

在創建Pair對象的while循環中有一個無限循環。這就是爲什麼你的內存不足。

我beleive你需要增加i和j在while循環的第一個條件：

while (i < sizeOfArray && j < sizeOfArray) 
{ 
    if (i != j && (array[j] - array[i] == diff)) 
    { 
     Pair newPair = new Pair(array[j], array[i]); 
     differencePairs.add(newPair); 

     // increment both here 
     i++; 
     j++; 
    } 

    // rest of loop 
}