Java的遞歸「找位」算法異常錯誤

給定兩個陣列具有獨特的整數元素，就是這麼元素內或兩個陣列之間重複：Java的遞歸「找位」算法異常錯誤

這是一個遞歸算法我寫的和需要幫助破譯錯誤我收到的消息。

public class Median { 
public static void main(String[] args) 
{ 
    int[] arr1 = new int[]{1,2,3,4,5}; 
    int[] arr2 = new int[]{6,7,8,9,10}; 
    medianOfBoth(arr1, arr2); 
} 

public static int medianOfBoth(int[] arr1, int[] arr2) 
{ 
    if (arr1.length <= 2 && arr2.length <= 2) 
    { 
     return compute_median(arr1, arr2); 
    } 

    else if (median(arr1) > median(arr2)) 
    { 
     //erase top half of arr1 and bottom half of arr2 
     arr1 = Arrays.copyOfRange(arr1, 0, median(arr1)); 
     arr2 = Arrays.copyOfRange(arr2, median(arr2), arr2.length - 1); 
     return medianOfBoth(arr1, arr2); 
    } 

    else // if (median(arr1) < median(arr2)) 
    { 
     arr1 = Arrays.copyOfRange(arr1, median(arr1), arr1.length - 1); 
     arr2 = Arrays.copyOfRange(arr2, 0, median(arr2)); 
     return medianOfBoth(arr1,arr2); 
    } 
} 

public static int median(int[] arr) 
{ 
    return arr[arr.length/2]; 
} 

public static int compute_median(int[] arr1, int[] arr2) 
{ 
    //arr1 and arr2 are either length 1 or 2 in this function 
    return (max(arr1[0], arr2[0]) + min(arr1[arr1.length-1], arr2[arr2.length-1]))/2; 
} 

public static int max(int x, int y) 
{ 
    if (x>y) 
     return x; 
    else 
     return y; 
} 

public static int min(int x, int y) 
{ 
    if (x<y) 
     return x; 
    else 
     return y; 
} 
}

這是我得到

Exception in thread "main" java.lang.IllegalArgumentException: 4 > 0 
at java.util.Arrays.copyOfRange(Arrays.java:2621) 
at Median.medianOfBoth(Median.java:28) 
at Median.medianOfBoth(Median.java:30) 
at Median.main(Median.java:8)

來源

2014-02-07 mharris7190

是否更改了錯誤信息你的代碼有點。請看看它。

import java.io.*; 

import java.util.*; 

public class Main { 

public static int median(int[] arr) 

{ 

    return arr[arr.length/2]; 
} 

public static int med(int[] arr) 
{ 
    return arr.length/2; 
} 

public static int max(int x, int y) 
{ 
    if (x>y) 
     return x; 
    else 
     return y; 
} 

public static int min(int x, int y) 
{ 
    if (x<y) 
     return x; 
    else 
     return y; 
} 

public static int compute_median(int[] arr1, int[] arr2) 
{ 
    //arr1 and arr2 are either length 1 or 2 in this function 
    return (max(arr1[0], arr2[0]) + min(arr1[arr1.length-1], arr2[arr2.length-1]))/2; 
} 

public static int medianOfBoth(int[] arr1, int[] arr2) 
{ 
    if (arr1.length <= 2 && arr2.length <= 2) 
    { 
     return compute_median(arr1, arr2); 
    } 

    else if (median(arr1) > median(arr2)) 
    { 
     //erase top half of arr1 and bottom half of arr2 
     //System.out.println("hi ="+med(arr2)+" "+arr2.length+"\n"); 
     arr1 = Arrays.copyOfRange(arr1, 0, med(arr1)); 
     arr2 = Arrays.copyOfRange(arr2, med(arr2), arr2.length); 
     return medianOfBoth(arr1, arr2); 
    } 

    else // if (median(arr1) < median(arr2)) 
    { 
     //System.out.println("bi ="+med(arr1)+" "+arr1.length+"\n"); 
     arr1 = Arrays.copyOfRange(arr1, med(arr1), arr1.length); 
     arr2 = Arrays.copyOfRange(arr2, 0, med(arr2)); 
     return medianOfBoth(arr1,arr2); 
    } 
} 

public static void main(String[] args) 
{ 
    int[] arr1 = new int[]{1,2,3,4,5}; 
    int[] arr2 = new int[]{1,3,5,7,9}; 
    System.out.println(medianOfBoth(arr1, arr2)); 
} 
}

來源

2014-02-07 02:43:49

實際上沒有按照它應該的方式工作。假設arr1 = {1,7,8,9,12}和arr2 = {2,3,4,90,100}。 medianOfBoth（arr1，arr2）返回5不是其中的一個元素。然而，你解決了我所感謝的主要問題！ – mharris7190

請看API爲Arrays.copyOfRange

arr1 = Arrays.copyOfRange(arr1, median(arr1), arr1.length - 1);

通過median(arr1)的返回值大於arr1.length - 1

來源

2014-02-07 02:22:53

Java的遞歸「找位」算法異常錯誤

回答

相關問題