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

Arnab Chakraborty

更新于：2020-12-23

123 次浏览

开启您的职业生涯

完成课程获得认证

开始学习