Java에서 k 정렬된 배열 병합

n개의 배열이 주어졌을 때, 정수형의 arr1[], arr2[], arr3[]의 3가지 배열을 취한다고 가정해 봅시다. 작업은 결과 배열이 런타임에만 정렬되도록 주어진 모든 정수 배열을 병합하는 것입니다.

예를 들어 이해하자

입력 -

정수

a[]={21,22,23,24};

정수 b[ ] ={28,31,35}

출력 −int 결과[ ]={21,22,23,24,28,31,35}.

설명 - 배열 요소는 결과 배열에서 적절한 위치에 따라 추가 및 추가되기 전에 비교됩니다.

입력 -

정수

a[]={1,3,5,7,9,11,13};

정수 b[ ] ={14,16,18}

정수 c[ ] ={19,20,21,22}

출력 - 정수 결과[ ]={1,3,5,7,9,11,13,14,16,18,19,20,21,22}.

설명 −배열 요소는 결과 배열에서 적절한 위치에 따라 추가 및 추가되기 전에 비교됩니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -

• arr1[], arr2[] 및 arr3[]과 같은 세 개의 정수 배열을 입력하고 결과 배열을 result[]로 입력하고 mergeSortedArray(new int[][] { arr1, arr2, arr3로 메서드 호출로 설정합니다. })

• mergeSortedArray(new int[][] { arr1, arr2, arr3 })

  메서드 내부

  • 우선순위 큐 유형의 큐와 astotal 변수를 생성하고 0으로 설정합니다.

  • i에서 0까지 FOR 루프를 시작하여 배열의 길이까지 배열의 버킷에서 요소를 queue로 선언된 변수에 추가하고 settotal을 total + arr[i].length로 추가합니다.

  • m을 0으로 설정하고 result[] 정수 배열을 선언합니다.

  • queue.isEmpty() =false일 때 시작한 다음 ArrayBucket ac toqueue.poll(), result[m++]를 ac.arr[ac.index]로 설정하고 ac.arr.length - 1보다 ac.indexless인 경우 IF를 확인한 다음 대기열을 설정합니다. add(newArrayBucket(ac.arr, ac.index + 1))

  • 반환 결과

예시

import java.util.Arrays;
import java.util.PriorityQueue;
class ArrayBucket implements Comparable<ArrayBucket>{
   int[] arr;
   int index;
   public ArrayBucket(int[] arr, int index){
      this.arr = arr;
      this.index = index;
   }
   @Override
   public int compareTo(ArrayBucket o){
      return this.arr[this.index] - o.arr[o.index];
   }
}
public class testClass{
   public static int[] mergeSortedArray(int[][] arr){
      PriorityQueue<ArrayBucket> queue = new
      PriorityQueue<ArrayBucket>();
      int total = 0;
      for (int i = 0; i < arr.length; i++){
         queue.add(new ArrayBucket(arr[i], 0));
         total = total + arr[i].length;
      }
      int m = 0;
      int result[] = new int[total];
      while (!queue.isEmpty()){
         ArrayBucket ac = queue.poll();
         result[m++] = ac.arr[ac.index];
         if (ac.index < ac.arr.length - 1){
            queue.add(new ArrayBucket(ac.arr, ac.index + 1));
         }
      }
      return result;
   }
   public static void main(String[] args){
      int[] arr1 = { 1, 3, 5, 7 };
      int[] arr2 = { 2, 4, 6, 8 };
      int[] arr3 = { 0, 9, 10, 11 };
      int[] result = mergeSortedArray(new int[][] { arr1, arr2, arr3 });
      System.out.println("The final merged sorted array is :- "+Arrays.toString(result));
   }
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.

The final merged sorted array is :-[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]