-1

このプログラムの目的は、再帰的および非再帰的な減少および征服型メソッ​​ドを使用して配列をソートせずに、配列内で k 番目に小さい要素を見つけることです。

誰かが私のコードを調べて、配列の範囲外エラーを解決してくれることを願っていました。

これらのエラーをスローしているメソッドは、非再帰的な選択が正常に機能する再帰的な選択です。

私のドライバーも添付されており、私のコードをテストしたい場合はすべてコンパイルする必要があります。

public class KthSmallest
{
private int counter;
private int term;
private int[] A;

int SelectionNonRecursive(int A[], int kthSmallest, int sizeOfA)
{   
    this.A = A;
    if(kthSmallest == 1 || kthSmallest == sizeOfA)
    {
        return (LinearSearch(kthSmallest, sizeOfA));
    }
    else
    {
        for(int i = 0; i<sizeOfA; i++)
        {
            counter = 0;
            for(int j = 0; j<sizeOfA; j++)
            {
                if(A[i] < A[j])
                {
                    counter++;
                }
            }
            if((sizeOfA - counter) == kthSmallest)
            {
                return A[i];
            }
        }
    }

    return 0;
}

int SelectionRecursive(int A[], int kthSmallest, int sizeOfA)
{
    this.A = A;
    return Selection_R(0, sizeOfA - 1, kthSmallest);
}

int Selection_R(int l, int r, int kthSmallest)
{
    if(l<r)
    {
    if(kthSmallest == 1 || kthSmallest == A.length)
    {
        return (LinearSearch(kthSmallest, A.length));
    }
    else
    {
        int s = LomutoPartition(l, r);
        if(s == kthSmallest - 1)
        {
            return A[s];
        }
        else if(s > (A[0] + kthSmallest - 1))
        {
            Selection_R(l, s-1, kthSmallest);
        }
        else
        {
            Selection_R(s+1, r, kthSmallest); 
        }
    }
    }
    return 0;
}

int LomutoPartition(int l, int r)
{
    int pivot = A[l];
    int s = l;
    for(int i = l+1; i<r; i++)
    {
        if(A[i] < pivot)
        {
            s += 1;
            swap(A[s], A[i]);
        }
    }
    swap(A[l], A[s]);
    return s;
}

public void swap(int i, int j)
{
    int holder = A[i];
    A[i] = A[j];
    A[j] = holder;
}

int LinearSearch(int kthSmallest, int sizeOfA)
{
    term = A[0];
    for(int i=1; i<sizeOfA; i++)
    {
        if(kthSmallest == 1)
        {
            if(term > A[i])
            {
                term = A[i];
            }
        }
        else
        {
            if(term < A[i])
            {
                term = A[i];
            }
        }
    }
    return term;
}
}

public class KthDriver
{
public static void main(String[] args)
{
    KthSmallest k1 = new KthSmallest();
    int[] array = {7,1,5,9,3};
    System.out.print(k1.SelectionRecursive(array, 3, array.length));


}
}
4

1 に答える 1

0

メソッド内で、LomutoPartitionメソッド内の配列要素を渡していますswap: -

swap(A[s], A[i]);  // Inside for loop

と

swap(A[l], A[s]);  // Outside for loop

そして、スワップメソッドはそれらを次のように見なしますindices: -

public void swap(int i, int j)  <-- // `i` and `j` are elements A[s] and A[i]
{
    int holder = A[i];  <-- // You are accessing them as indices(A[i] -> A[A[s]])
    A[i] = A[j];
    A[j] = holder;
}

そのため、その例外が発生しています。配列内のいずれかの要素がサイズより大きい場合、爆発するためです。

呼び出しを次のように変更する必要があります: -

swap(s, i);   // Inside for loop

と

swap(l, s);   // Outside for loop

それぞれ。そして、あなたの方法をそのままにしておいてください。

配列要素ではなく、配列インデックスを渡す必要があることに注意してください。配列要素を渡すと、メソッドでのスワップは配列に反映されません。メソッドには独自の要素のコピーがあるためです。

于 2012-11-08T06:26:17.633 に答える