경계 밖으로 배열

Question

이 프로그램의 목적은 재귀 및 비 재귀 감소 및 정복 유형 방법을 사용하여 배열을 정렬하지 않고 배열에서 k 번째로 작은 요소를 찾는 것입니다.

누군가 내 코드를 살펴보고 배열 범위를 벗어난 배열 오류로 나를 도울 수 있기를 바랬습니다.

이러한 오류가 발생하는 메서드는 비 재귀 선택이 올바르게 작동하는 재귀 선택입니다.

내 코드를 테스트하려면 내 드라이버가 첨부되어 있고 모든 것이 컴파일되어야합니다.

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

및

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

그리고 스왑 방법은 indices로 간주 : - - : 당신의 LomutoPartition 방법 내부

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

, 당신은 당신의 swap 방법으로 배열 요소를 전달하는

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 

각각. 그리고 당신의 방법을 그대로 두십시오.

배열 요소가 아니라 배열 인덱스를 전달해야합니다. 배열 요소를 전달하면 메서드에서의 스와핑은 배열에 반영되지 않습니다. 왜냐하면, 당신의 메소드는 당신 자신의 요소 사본을 가질 것이기 때문입니다.