-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 回答