サブセットの処理 - 配列の相違

Question

配列を取るプログラムを作成しようとしていて、配列を効率的に並べ替えると、ソートされた配列内の各ペアに対して、指定された相違点を整数パラメータで渡しますメソッド内のパラメーター）、指定された差異に基づいてペアを出力します。メソッドは効果的に、異なる整数ペアを持つ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()); 
     } 
    }    
} 

とこの次のクラスはあなたが不思議に思っている場合のペアクラスです。私が間違っているところを親切に教えてください。ありがとう！

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

whileループには、ペアオブジェクトを作成する無限ループがあります。だからこそあなたは記憶がなくなってしまったのです。

私は、whileループの最初の状態でiとjをインクリメントする必要があります信じて：

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 
}