ค้นหาผลรวมที่น้อยที่สุด Kth ของเมทริกซ์ที่มีการเรียงลำดับแถวใน C++

สมมติว่าเรามีเมทริกซ์ m * n หนึ่งชื่อเรียกว่า mat และจำนวนเต็ม k mat มีแถวเรียงตามลำดับที่ไม่ลดลง เราสามารถเลือกหนึ่งองค์ประกอบจากแต่ละแถวเพื่อสร้างอาร์เรย์ได้ เราต้องหาผลรวมอาร์เรย์ที่เล็กที่สุด Kth ในบรรดาอาร์เรย์ที่เป็นไปได้ทั้งหมด

ดังนั้น หากอินพุตเป็นเหมือน mat =[[1,3,11],[2,4,6]]

และ k =5 ผลลัพธ์จะเป็น 7 เนื่องจากเมื่อเราเลือกหนึ่งองค์ประกอบจากแต่ละแถว ผลรวมที่น้อยที่สุดของ k ตัวแรกคือ [1,2], [1,4], [3,2], [3,4] , [1,6]. ผลรวมที่ 5 คือ 7.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดลำดับความสำคัญหนึ่งคิว pq

• กำหนดอาร์เรย์ 2 มิติหนึ่งรายการ m

• กำหนดฟังก์ชัน update() ซึ่งจะใช้อาร์เรย์ v, i, ok เริ่มต้นด้วย false

• ถ้าฉันมีขนาดเท่ากับ v แล้ว −

  • ถ้าตกลงเป็นเท็จ −

    • กลับ

  • กลับ

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของ v อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ −

    • ผลรวม :=ผลรวม + m[j, v[j]]

  • กำหนดอาร์เรย์ชั่วคราวและคัดลอก v ลงไป

  • ใส่ผลรวมลงใน temp ที่จุดเริ่มต้น

  • ใส่อุณหภูมิลงใน pq

  • กลับ

• (เพิ่ม v[i] ขึ้น 1)

• ถ้า ok เป็นเท็จ และ v[i]

  • อัปเดต (v, i + 1, จริง)

• อัปเดต (v, i + 1, จริง)

• อัปเดต (v, i + 1, ตกลง)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• m :+ เมทริกซ์ที่กำหนด

• ยกเลิก :=0

• n :=จำนวนแถวของ m

• z :=จำนวนคอลัมน์ของ m

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ret :=ret + m[i, 0]

• กำหนดอุณหภูมิอาร์เรย์ของขนาด n

• ใส่ ret ลงใน temp ที่จุดเริ่มต้น

• ใส่อุณหภูมิลงใน pq

• กำหนดหนึ่งชุด s

• ในขณะที่ k ไม่ใช่ศูนย์ ให้ลด k ลง 1 ในการวนซ้ำแต่ละครั้ง ทำ -

  • กำหนดอาร์เรย์ temp =ด้านบนของ pq

  • ลบองค์ประกอบออกจาก pq

  • ใส่อุณหภูมิลงใน s

  • ret :=temp[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}}

ผลลัพธ์

7