Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 크기가 다른 k개의 정렬된 배열 병합

<시간/>

다른 k개의 정렬된 배열이 있다고 가정합니다. 이 배열을 병합하고 정렬된 결과를 표시해야 합니다.

따라서 입력이 k =3이고 배열이 {2, 4},{3, 5, 7},{1, 10, 11, 12} 이면 출력은 1 2 3 4 5 7 10 11이 됩니다. 12

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 첫 번째 요소는 정수이고 두 번째 요소는 또 다른 정수 쌍으로 정의합니다. 이름을 ppi로 지정합니다.
  • 배열 연산 정의
  • 하나의 우선순위 대기열 q 정의
  • 초기화 i의 경우:=0, i
  • q에 (arr[i, 0], {i, 0}) 삽입
  • q가 비어 있지 않은 동안 −
    • current_element :=q의 최상위 요소
    • q에서 요소 삭제
    • i :=current_element의 두 번째 요소
    • j :=current_element의 세 번째 요소
    • op 마지막에 current_element의 첫 번째 요소 삽입
    • j + 1
    • q에 (arr[i, j+1], {i, j+1}) 삽입
  • 반환 작업
  • 예시

    이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

    #include <bits/stdc++.h>
    using namespace std;
    #define ppi pair<int,pair<int,int>>
    vector<int> merge(vector<vector<int> > arr){
       vector<int> op;
       priority_queue<ppi, vector<ppi>, greater<ppi> > queue;
       for (int i = 0; i < arr.size(); i++)
       queue.push({ arr[i][0], { i, 0 } });
       while (queue.empty() == false) {
          ppi current_element = queue.top();
          queue.pop();
          int i = current_element.second.first;
          int j = current_element.second.second;
          op.push_back(current_element.first);
          if (j + 1 < arr[i].size())
          queue.push({ arr[i][j + 1], { i, j + 1 } });
       }
       return op;
    }
    int main(){
       vector<vector<int> > arr{ { 2,4}, { 3,5,7 }, { 1, 10, 11, 12 } };
       vector<int> output = merge(arr);
       for(int i = 0; i<output.size(); i++)
       cout << output[i] << " ";
    }

    입력

    {{ 2,4}, { 3,5,7 }, { 1, 10, 11, 12 }}

    출력

    1 2 3 4 5 7 10 11 12