Array Out Of Bounds

Question

Le but de ce programme est de trouver le kième élément le plus petit d'un tableau sans trier le tableau en utilisant une méthode de décroissance et de conquête récursives et non récurrentes. J'espérais que quelqu'un pourrait regarder au-dessus de mon code et essayer de m'aider avec mon tableau hors limites erreur (s).

La méthode qui lance ces erreurs est la sélection récursive que la sélection non récursive fonctionne correctement.

Mon pilote est également attaché et tout devrait se compiler si vous voulez tester mon code.

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

l'intérieur de votre méthode LomutoPartition, vous passez les éléments du tableau dans votre méthode swap: -

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

et

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

Et votre méthode d'échange les considère comme 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; 
} 

C'est pourquoi vous obtenez cette exception. Parce que, si un élément de tableau est supérieur à la taille, il va exploser.

Vous devez changer votre appel à: -

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

et

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

respectivement. Et laissez votre méthode telle qu'elle est. Notez que vous devez passer des indices de tableau et non des éléments de tableau. Si vous transmettez des éléments de tableau, la permutation de la méthode ne sera pas reflétée dans votre tableau. Parce que votre méthode aura sa propre copie de vos éléments.