資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式：查詢不同列表中選取元素之間的最小差值
假設我們有一系列列表，我們需要找到透過從每個列表中選擇一個值並計算選定元素的最大值和最小值之差而形成的最小差值。
因此，如果輸入類似於 lists = [ [30, 50, 90], [85], [35, 70]]，則輸出將為 20，因為我們可以取 90、85、70，而 90 - 70 = 20
為了解決這個問題，我們將遵循以下步驟：
maxVal := -∞
ret := ∞
定義一個優先佇列 pq
n := 列表的大小
對於初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
對陣列 lists[i] 進行排序
將 {lists[i, 0], i, 0} 插入 pq
maxVal := lists[i, 0] 和 maxVal 的最大值
當 pq 的大小與 n 相同時，執行：
定義一個數組 temp = pq 的頂部元素
從 pq 中刪除頂部元素
ret := ret 和 (maxVal - temp[0]) 的最小值
增加 temp 的最後一個元素
如果 temp 的最後一個元素 < lists[temp[1]] 的大小，則：
maxVal := maxVal 和 lists[temp[1], temp 的最後一個元素] 的最大值
temp[0] := lists[temp[1], temp 的最後一個元素]
將 temp 插入 pq
返回 ret
示例
讓我們看看下面的實現以更好地理解：
#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
更新於：2020-12-23
123 次瀏覽
廣告