使用子集 - 成对差异（数组）

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 
}