Arbeiten mit Subsets - Unterschied in Paaren (Array)

Question

Ich versuche, ein Programm zu schreiben, das ein Array nimmt, sortiert das Array effektiv viaquickSort, dann für jedes Paar im sortierten Array mit einer angegebenen Differenz von einem Ganzzahlparameter (über der Parameter in der Methode), gibt es Paare basierend auf der angegebenen Differenz aus. Die Methode gibt effektiv eine ArrayList mit ganzzahligen Paaren zurück, die unterschiedlich sind. Z.B. Nehmen wir an, ich habe ein Array wie {16, 12, 7, 8, 4, 13, 9, 20}. Das Verfahren würde es dann sortieren, wenn die übergebene ganze Zahl 4 ist, die Paare es

(4,8) (8,12) (9,13) (12,16) (16,20) zurückkehren würde

sind obwohl

Aus irgendeinem Grund mein Code tut das nicht, ich erhalte einen Laufzeitfehler:

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) 

Hier ist mein Code, und was ich getan habe:

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

und Diese nächste Klasse ist die Klasse für den Fall, dass Sie sich fragen. Bitte sag mir, wo ich falsch liege. Vielen Dank!

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

Sie haben eine Endlosschleife in der while-Schleife, die die Pair-Objekte erstellt. Deshalb hast du keine Speicher mehr.

Ich glaube, Sie i und j in der ersten Bedingung der while-Schleife erhöhen müssen:

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 
}