โปรแกรมค้นหาความแตกต่างที่เล็กที่สุดระหว่างองค์ประกอบที่เลือกจากรายการต่าง ๆ ใน C++

สมมติว่าเรามีรายการของรายการ เราต้องหาความแตกต่างที่น้อยที่สุดที่สามารถเกิดขึ้นได้โดยการเลือกค่าหนึ่งค่าจากแต่ละรายการและหาผลต่างระหว่างจำนวนสูงสุดและต่ำสุดขององค์ประกอบที่เลือก

ดังนั้นหากอินพุตเป็นเหมือนรายการ =[ [30, 50, 90], [85], [35, 70]] ผลลัพธ์จะเป็น 20 ตามที่เราสามารถหาได้ 90, 85, 70 และ 90 - 70 =20

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

• maxVal :=-inf

• ret :=inf

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

• n :=ขนาดของรายการ

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

  • จัดเรียงรายการอาร์เรย์[i]

  • แทรก {lists[i, 0], i, 0} ลงใน pq

  • maxVal :=สูงสุดของรายการ[i, 0] และ maxVal

• ในขณะที่ขนาดของ pq เท่ากับ n ให้ทำ -

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

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

  • ret :=ขั้นต่ำของ ret และ (maxVal - temp[0])

  • เพิ่มองค์ประกอบสุดท้ายของอุณหภูมิ

  • ถ้าองค์ประกอบสุดท้ายของ temp <ขนาดของรายการ[temp[1]] แล้ว

    • maxVal :=สูงสุดของ maxVal และรายการ[temp[1] องค์ประกอบสุดท้ายของ temp]

    • temp[0] :=รายการ[temp[1] องค์ประกอบสุดท้ายของ temp]

    • ใส่อุณหภูมิลงใน 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:
   int solve(vector<vector<int>>& lists) {
      int maxVal = INT_MIN;
      int ret = INT_MAX;
      priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
      int n = lists.size();
      for (int i = 0; i < n; i++) {
         sort(lists[i].begin(), lists[i].end());
         pq.push({lists[i][0], i, 0});
         maxVal = max(lists[i][0], maxVal);
      }
      while (pq.size() == n) {
         vector<int> temp = pq.top();
         pq.pop();
         ret = min(ret, maxVal - temp[0]);
         temp.back()++;
         if (temp.back() < lists[temp[1]].size()) {
            maxVal = max(maxVal, lists[temp[1]][temp.back()]);
            temp[0] = lists[temp[1]][temp.back()];
            pq.push(temp);
         }
      }
      return ret;
   }
};
int solve(vector<vector<int>>& lists) {
   return (new Solution())->solve(lists);
}
int main(){
   vector<vector<int>> v = {{30, 50, 90},{85},{35, 70}};
   cout << solve(v);
}

อินพุต

{{30, 50, 90},{85},{35, 70}}

ผลลัพธ์

20