-2

このコードは、整数の配列のピーク番号を見つけることです。問題は、エラーが発生することException in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7です。

public long DivideAndConquer(int lo,int hi)
{
  int mid=((lo+hi)-1)/2;
   if(myarray[mid]>=myarray[mid-1]&&myarray[mid]>= myarray[mid+1])
     return myarray[mid];
   else if (myarray[mid-1]>= myarray[mid])
     return DivideAndConquer(lo,mid-1);
   else if (myarray[mid]<=myarray[mid+1])
     return DivideAndConquer(mid+1,hi);
return 99;

}

ピーク数は、隣接する数よりも大きい数であり、配列の最後または最初にいる場合は、プレビュー要素のみを探す必要があります。

最後の位置にある要素がプレビューよりも大きい場合はピークであるため、このエラーが発生すると思います。たとえば、私の最後の位置は 9で、その後はピークですが、最初の if ステートメントでは、持っていないものmyarray[9] > myarray[8]も検索されるため、このエラーが発生します。myarray[9+1]

最初のステートメントを削除&&して「または」（||）を追加することはできません。これは、間違った答えが得られるためです。アイデアはありますか？

4

3 に答える 3

1

あなたが言ったように、問題はあなたの実装が配列の最後の項目でmid + 1あるindex を見ようとすることです。midこのケースを処理する必要があります。次のようなもの：

public long DivideAndConquer(int lo,int hi){
    int mid = (lo+hi) / 2; //Modified to select the middle item
    if(mid + 1 >= myarray.length){
        //TODO: Handle the case when mid is the index of the last item in the array
    } else if(mid - 1 < 0){
        //TODO: Handle the case when mid is the index of the first item in the array
    } else if(myarray[mid]>=myarray[mid-1]&&myarray[mid]>= myarray[mid+1]){
        return myarray[mid];
    } else if (myarray[mid-1]>= myarray[mid]){
        return DivideAndConquer(lo,mid-1);
    } else if (myarray[mid]<=myarray[mid+1]){
        return DivideAndConquer(mid+1,hi);'
    }
    return Long.MIN_VALUE; //Probably a more suitable error indicator than 99
    //Alternatively, an exception could be thrown
}

上記で提案したアプローチを使用する場合は、mid - 1 < 0andmid + 1 >= myarray.lengthケースの処理を実装する際に特に注意してください。がまたはmyarray.lengthのみの場合は、特別な処理が必要になる場合があります。12

于 2013-05-03T11:58:14.827 に答える
0

「if-else-if-」... 構造のような決定カスケードを実装する場合、すべてのケースが処理されることを確認する必要があります。

また、計算された配列インデックスが指定された配列に対して有効であることを確認する必要があります。この要件により、さらに「if」ステートメントが導入される場合があります。

あなたのテキストでは、「私が配列の最後または最初にいる場合」と書いていますが、コードにはこれらの条件をチェックする「ifステートメント」はありません。

于 2013-05-03T11:03:08.500 に答える
0

アルゴリズムの正しさを考慮せずに、インデックスを安全に作成するために次の変更を行いました。

public long DivideAndConquer(int lo,int hi)
{
    int mid=(lo+hi)/2; // Valid range
    if((lo<mid||myarray[mid]>=myarray[mid-1])
                 &&(hi>mid||myarray[mid]>= myarray[mid+1]))
       return myarray[mid];
    else if (lo<mid&&yarray[mid-1]>= myarray[mid])
       return DivideAndConquer(lo,mid-1);
    else if (hi>mid&&myarray[mid]<=myarray[mid+1])
       return DivideAndConquer(mid+1,hi);
    return 99;
}
于 2013-05-03T10:57:38.657 に答える