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)，因此可以忽略。