나이브 방법

Question

내가 k는 의도적으로 순진 방법으로 배열 (N 요소와 각을) 분류 병합하는 알고리즘을 구현하기 위해 노력하고있어 :

단계 :

1. 첫 번째 및 두 번째 배열을 병합
2. 위의 결과 배열을 세 번째 배열로 병합
3. 위의 결과 배열을 네 번째 배열로 병합
,451,515,
4. ... 등의 K 번째 어레이

내 코드 출력 3 × 3, 4 × 4, 5 × 5의 2 차원 배열, 그러나 그것 stucks 대한 정렬 된 단일 어레이는 2 차원 어레이가 될 수있는 좁은 병합까지 .

코드의 복잡성이 너무 좋지 않아서 컴파일하는 데 너무 오래 걸리는가? 아니면 내가 모르는 바보 같은 논리 오류가 있습니까?

나는 내 코드를 읽고 "< < < ===="으로 표시된 줄이 문제라고 생각합니다. " 어떻게해야 제대로 할 수 있습니까? 아무것도 "병합 후 :"마지막 행 다음에 표시되지 않습니다 :하지만 나는 그것을 강제로 종료 될 때까지 프로그램이 계속 실행되고

public class Merge { 

    // merge 2 arrays into a single sorted array 
    private static int[] merge(int[] arrayA, int[] arrayB) { 
     int n1 = arrayA.length;  // number of elements in arrayA 
     int n2 = arrayB.length;  // number of elements in arrayB 
     int[] mergeArray = new int[n1+n2]; 

     int i = 0;  // pointer of current index in mergeArray 
     int p1 = 0;  // pointer of current index in arrayA 
     int p2 = 0;  // pointer of current index in arrayB 
     while (p1 < n1 && p2 < n2) { 
      // put the lowest number the mergeArray until one of the array is done 
      if (arrayA[p1] < arrayB[p2]) { 
       mergeArray[i] = arrayA[p1]; 
       i++; 
       p1++; 
      } 
      else if (arrayB[p2] < arrayA[p1]) { 
       mergeArray[i] = arrayB[p2]; 
       i++; 
       p2++; 
      } 
     } 
     // if all elements of arrayA is copied to mergeArray, then copy remaining elements in arrayB to it 
     if (p1 >= n1) { 
      for (int j = p2; j < arrayB.length; j++) { 
       mergeArray[i] = arrayB[j]; 
       i++; 
      } 
     } 
     // if all elements of arrayB is copied to mergeArray, then copy remaining elements in arrayA to it 
     if (p2 >= n2) { 
      for (int j = p1; j < arrayA.length; j++) { 
       mergeArray[i] = arrayA[j]; 
       i++; 
      } 
     } 
     return mergeArray; 
    } 

    public static int[] naiveMerge(int[][] data) { 
     int k = data.length;  // number of sorted array 
     int n = data[0].length;  // number of elements in each array 
     int[] resultArray = new int[k*n]; 

     int[] tempArray = Merge.merge(data[0], data[1]); // merge the first two arrays 
     for (int i = 2; i < k; i++) { 
      // then merge in the third, fourth ... k arrays 
      tempArray = Merge.merge(tempArray, data[i]); // <<<==== ?? 
      resultArray = tempArray; 
     } 
     return resultArray; 
    } 
} 

프로그램

이 좋아하는이 붙어.

Answer 1

3, 4 및 5에 해당하는 배열을 보면 모든 배열의 모든 값이 고유하다는 것을 알 수 있습니다. 그러나 귀하의 6 경우에는 중복 된 값이 있음을 알 수 있습니다 (두 개의 46이 있습니다). 첫 번째 while 루프를 따라 추적하십시오 (merge). 어느 시점에서 두 배열의 값이 같은 경우 어떻게됩니까?

행운을 빈다.