สมมติว่าเรามีรายการของรายการ เราต้องหาความแตกต่างที่น้อยที่สุดที่สามารถเกิดขึ้นได้โดยการเลือกค่าหนึ่งค่าจากแต่ละรายการและหาผลต่างระหว่างจำนวนสูงสุดและต่ำสุดขององค์ประกอบที่เลือก
ดังนั้นหากอินพุตเป็นเหมือนรายการ =[ [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