LeetCode-632 Smallest Range Covering Elements from K Lists

Description

给定\(k\)个数组，从每个数组中各取最少一个数，使得取的数当中最大值与最小值之差最小

Constraints

• \(1 \le k \le 3500\)
• \(1 \le nums[i].length \le 50\)

Solution

将所有数都放到一个数组中，标好归属的原数组编号并排序，然后跑一遍滑动窗口即可

Code

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<tuple<int, int>> vec;
        for(size_t i = 0; i < nums.size(); ++i) {
            for(auto v : nums[i]) {
                vec.emplace_back(v, i);
            }
        }
        ranges::sort(vec);

        int c = 0;
        int cnt[3505] {};
        int res = 1<<30;
        vector<int> best;

        for(int l = 0, r = 0; l < vec.size(); ++l) {
            while(r < vec.size() && c < nums.size()) {
                auto [_, idx] = vec[r++];
                if(!cnt[idx]++) c++;
            }
            if(c == nums.size()) {
                int old = res;
                int v1 = get<0>(vec[l]);
                int v2 = get<0>(vec[r-1]);
                res = min(res, v2 - v1);
                if(old != res) best = {v1, v2};
            }
            auto [_, idx] = vec[l];
            if(!--cnt[idx]) c--;
        }
        return best;
    }
};

Link

LeetCode-632 Smallest Range Covering Elements from K Lists