数组超出范围

Question

该程序的目的是在数组中使用递归和非递归减少和征服类型方法来查找第k个最小元素。

我希望有人可以看看我的代码，并试图帮助我与我的数组越界的错误（S）。

抛出这些错误的方法是非递归选择正常工作的递归选择。

我的驱动程序也附加，如果你想测试我的代码，所有东西都应该编译。

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)); 


} 
} 

Answer 1

里面你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 

。并保持原样。

请注意，您应该传递数组索引，而不是数组元素。如果你传递数组元素，那么方法中的交换将不会反映在你的数组中。因为，你的方法将有自己的元素副本。