LeetCode-632. Smallest Range Covering Elements from K Lists [C++][Java]

目录

题目描述

解题思路

【C++】

【Java】

LeetCode-632. Smallest Range Covering Elements from K Listshttps://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/description/

题目描述

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Constraints:

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -105 <= nums[i][j] <= 105
• nums[i] is sorted in non-decreasing order.

解题思路

【C++】

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int n = nums.size(), xmin = INT_MAX, xmax = INT_MIN;
        unordered_map<int, vector<int>> indices;
        for (int i = 0; i < n; i++) {
            for (const int& num : nums[i]) {
                indices[num].push_back(i);
                xmin = min(xmin, num);
                xmax = max(xmax, num);
            }
        }
        vector<int> freq(n);
        int in = 0, l = xmin, r = xmin - 1, ansL = xmin, ansR = xmax;
        while (r < xmax) {
            if (!indices.count(++r)) {continue;}
            for (const int& i : indices[r]) {
                ++freq[i];
                if (freq[i] == 1) {++in;}
            }
            while (in == n) {
                if (r - l < ansR - ansL) {
                    ansR = r;
                    ansL = l;
                }
                if (indices.count(l)) {
                    for (const int& i : indices[l]) {
                        --freq[i];
                        if (freq[i] == 0) {--in;}
                    }
                }
                ++l;
            }
        }
        return {ansL, ansR};
    }
};

【Java】

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int n = nums.size(), xmin = Integer.MAX_VALUE, xmax = Integer.MIN_VALUE;
        Map<Integer, List<Integer>> indices = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < n; i++) {
            for (int num : nums.get(i)) {
                List list = indices.getOrDefault(num, new ArrayList<Integer>());
                list.add(i);
                indices.put(num, list);
                xmin = Math.min(xmin, num);
                xmax = Math.max(xmax, num);
            }
        }
        int[] freq = new int[n];
        int in = 0, l = xmin, r = xmin - 1, ansL = xmin, ansR = xmax;
        while (r < xmax) {
            if (!indices.containsKey(++r)) {continue;}
            for (int i : indices.get(r)) {
                ++freq[i];
                if (freq[i] == 1) {++in;}
            }
            while (in == n) {
                if (r - l < ansR - ansL) {
                    ansR = r;
                    ansL = l;
                }
                if (indices.containsKey(l)) {
                    for (int i : indices.get(l)) {
                        --freq[i];
                        if (freq[i] == 0) {--in;}
                    }
                }
                ++l;
            }
        }
        return new int[]{ansL, ansR};
    }
}

复杂度分析

时间复杂度：O(nk+∣V∣)，其中 n 是所有列表的平均长度，k 是列表数量，∣V∣ 是列表中元素的值域，在本题中 ∣V∣≤2∗10^5。构造哈希映射的时间复杂度为 O(nk)，双指针的移动范围为 ∣V∣，在此过程中会对哈希映射再进行一次遍历，时间复杂度为 O(nk)，因此总时间复杂度为 O(nk+∣V∣)。

空间复杂度：O(nk)，即为哈希映射使用的空间。哈希映射的「键」的数量由列表中的元素个数 nk 以及值域 ∣V∣ 中的较小值决定，「值」为长度不固定的数组，但是它们的长度之和为 nk，因此哈希映射使用的空间为 O(nk)。在使用双指针时，还需要一个长度为 n 的数组，其对应的空间在渐进意义下小于 O(nk)，因此可以忽略。