C++에서 정렬된 행이 있는 행렬의 K번째 가장 작은 합 찾기

mat라고 하는 하나의 m * n 행렬과 정수 k가 있다고 가정하고 mat에는 내림차순으로 정렬된 행이 있습니다. 배열을 형성하기 위해 각 행에서 정확히 하나의 요소를 선택할 수 있습니다. 가능한 모든 배열 중에서 K번째로 작은 배열 합을 찾아야 합니다.

따라서 입력이 mat =[[1,3,11],[2,4,6]]

와 같은 경우

1	3	1 1
2	4	6

k =5이면 출력은 7이 됩니다. 각 행에서 하나의 요소를 선택할 때 처음 k개의 가장 작은 합은 [1,2], [1,4], [3,2], [3,4]입니다. , [1,6]. 여기서 5번째 합은 7입니다.

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

하나의 우선순위 큐 pq 정의
하나의 2D 배열 정의
update() 함수를 정의하면 배열 v, i, ok가 false로 초기화됩니다.
i가 v의 크기와 같으면 -
- ok가 거짓이면 -
  - 반환
- 반환
- j 초기화의 경우:=0, j
  - 합계 :=합계 + m[j, v[j]]
- 배열 temp를 정의하고 v를 복사하십시오.
- 시작 부분에 합계를 temp에 삽입
- pq에 temp 삽입
- 반환
(v[i]를 1만큼 증가)
ok가 거짓이고 v[i]
- 업데이트(v, i + 1, true)
업데이트(v, i + 1, true)
업데이트(v, i + 1, 확인)
주요 방법에서 다음을 수행하십시오 -
m :+ 주어진 행렬
ret :=0
n :=m의 행 수
z :=m의 열 수
initialize i :=0의 경우, i
- 렛 :=렛 + m[i, 0]
n
크기의 어레이 온도 정의
처음에 temp에 ret를 삽입
pq에 temp 삽입
한 세트 정의
k가 0이 아닌 동안 각 반복에서 k를 1씩 감소시키고 -
- 배열 정의 temp =pq의 상단
- pq에서 요소 삭제
- s에 temp 삽입
- ret :=온도[0]
- temp에서 temp의 첫 번째 요소 삭제
- 업데이트(온도, 0)
- 동안(pq가 비어 있지 않고 pq의 맨 위 요소가 s의 구성원이 아님) 다음을 수행합니다. -
  - pq에서 요소 삭제
리턴 렛

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

예시

#include <bits/stdc++.h>
using namespace std;
struct Cmp{
   bool operator()(vector <int>& a, vector <int>& b) {
      return !(a[0] < b[0]);
   }
};
class Solution {
   public:
   priority_queue<vector<int>, vector<vector<int> >, Cmp> pq;
   vector<vector<int> > m;
   int z;
   void update(vector<int>& v, int i, bool ok = false){
      if (i == v.size()) {
         if (!ok)
         return;
         int sum = 0;
         for (int j = 0; j < v.size(); j++) {
            sum += m[j][v[j]];
         }
         vector<int> temp(v.begin(), v.end());
         temp.insert(temp.begin(), sum);
         pq.push(temp);
         return;
      }
      v[i]++;
      if (!ok && v[i] < z)
      update(v, i + 1, true);
      v[i]--;
      update(v, i + 1, ok);
   }
   int kthSmallest(vector<vector<int> >& m, int k){
      this->m = m;
      int ret = 0;
      int n = m.size();
      z = m[0].size();
      for (int i = 0; i < n; i++) {
         ret += m[i][0];
      }
      vector<int> temp(n);
      temp.insert(temp.begin(), ret);
      pq.push(temp);
      set<vector<int> > s;
      while (k--) {
         vector<int> temp = pq.top();
         pq.pop();
         s.insert(temp);
         ret = temp[0];
         temp.erase(temp.begin());
         update(temp, 0);
         while (!pq.empty() && s.count(pq.top())) {
            pq.pop();
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,3,11},{2,4,6}};
   cout << (ob.kthSmallest(v, 5));
}

입력

{{1,3,11},{2,4,6}}