class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
}
};
632. 最小区间
你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1：
输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] 输出：[20,24] 解释： 列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。 列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。 列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
示例 2：
输入：nums = [[1,2,3],[1,2,3],[1,2,3]] 输出：[1,1]
提示：
nums.length == k1 <= k <= 35001 <= nums[i].length <= 50-105 <= nums[i][j] <= 105nums[i] 按非递减顺序排列
原站题解
javascript 解法, 执行用时: 348 ms, 内存消耗: 101.1 MB, 提交时间: 2024-11-24 00:13:22
/**
* @param {number[][]} nums
* @return {number[]}
*/
var smallestRange = function(nums) {
const size = nums.length;
const indices = new Map();
let xMin = Number.MAX_SAFE_INTEGER, xMax = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < size; i++) {
for (const x of nums[i]) {
if (!indices.has(x)) {
indices.set(x, []);
}
indices.get(x).push(i);
xMin = Math.min(xMin, x);
xMax = Math.max(xMax, x);
}
}
const freq = new Array(size).fill(0);
let inside = 0;
let left = xMin, right = xMin - 1;
let bestLeft = xMin, bestRight = xMax;
while (right < xMax) {
right++;
if (indices.has(right)) {
for (const x of indices.get(right)) {
freq[x]++;
if (freq[x] === 1) {
inside++;
}
}
while (inside === size) {
if (right - left < bestRight - bestLeft) {
bestLeft = left;
bestRight = right;
}
if (indices.has(left)) {
for (const x of indices.get(left)) {
freq[x]--;
if (freq[x] === 0) {
inside--;
}
}
}
left++;
}
}
}
return [bestLeft, bestRight];
};
java 解法, 执行用时: 129 ms, 内存消耗: 101.4 MB, 提交时间: 2024-11-24 00:13:04
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int size = nums.size();
Map<Integer, List<Integer>> indices = new HashMap<Integer, List<Integer>>();
int xMin = Integer.MAX_VALUE, xMax = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
for (int x : nums.get(i)) {
List<Integer> list = indices.getOrDefault(x, new ArrayList<Integer>());
list.add(i);
indices.put(x, list);
xMin = Math.min(xMin, x);
xMax = Math.max(xMax, x);
}
}
int[] freq = new int[size];
int inside = 0;
int left = xMin, right = xMin - 1;
int bestLeft = xMin, bestRight = xMax;
while (right < xMax) {
right++;
if (indices.containsKey(right)) {
for (int x : indices.get(right)) {
freq[x]++;
if (freq[x] == 1) {
inside++;
}
}
while (inside == size) {
if (right - left < bestRight - bestLeft) {
bestLeft = left;
bestRight = right;
}
if (indices.containsKey(left)) {
for (int x: indices.get(left)) {
freq[x]--;
if (freq[x] == 0) {
inside--;
}
}
}
left++;
}
}
}
return new int[]{bestLeft, bestRight};
}
}
rust 解法, 执行用时: 142 ms, 内存消耗: 22.4 MB, 提交时间: 2024-11-24 00:12:44
use std::collections::HashMap;
impl Solution {
pub fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
let size = nums.len();
let mut indices: HashMap<i32, Vec<usize>> = HashMap::new();
let mut x_min = i32::MAX;
let mut x_max = i32::MIN;
for i in 0..size {
for &x in &nums[i] {
indices.entry(x).or_insert_with(Vec::new).push(i);
x_min = x_min.min(x);
x_max = x_max.max(x);
}
}
let mut freq = vec![0; size];
let mut inside = 0;
let mut left = x_min;
let mut right = x_min - 1;
let mut best_left = x_min;
let mut best_right = x_max;
while right < x_max {
right += 1;
if let Some(vec) = indices.get(&right) {
for &x in vec {
freq[x] += 1;
if freq[x] == 1 {
inside += 1;
}
}
while inside == size {
if right - left < best_right - best_left {
best_left = left;
best_right = right;
}
if let Some(vec) = indices.get(&left) {
for &x in vec {
freq[x] -= 1;
if freq[x] == 0 {
inside -= 1;
}
}
}
left += 1;
}
}
}
vec![best_left, best_right]
}
}
golang 解法, 执行用时: 124 ms, 内存消耗: 6.9 MB, 提交时间: 2023-05-16 11:26:34
func smallestRange(nums [][]int) []int {
size := len(nums)
indices := map[int][]int{}
xMin, xMax := math.MaxInt32, math.MinInt32
for i := 0; i < size; i++ {
for _, x := range nums[i] {
indices[x] = append(indices[x], i)
xMin = min(xMin, x)
xMax = max(xMax, x)
}
}
freq := make([]int, size)
inside := 0
left, right := xMin, xMin - 1
bestLeft, bestRight := xMin, xMax
for right < xMax {
right++
if len(indices[right]) > 0 {
for _, x := range indices[right] {
freq[x]++
if freq[x] == 1 {
inside++
}
}
for inside == size {
if right - left < bestRight - bestLeft {
bestLeft, bestRight = left, right
}
for _, x := range indices[left] {
freq[x]--
if freq[x] == 0 {
inside--
}
}
left++
}
}
}
return []int{bestLeft, bestRight}
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
python3 解法, 执行用时: 744 ms, 内存消耗: 21.5 MB, 提交时间: 2023-05-16 11:26:13
# 哈希表+滑动窗口
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
n = len(nums)
indices = collections.defaultdict(list)
xMin, xMax = 10**9, -10**9
for i, vec in enumerate(nums):
for x in vec:
indices[x].append(i)
xMin = min(xMin, *vec)
xMax = max(xMax, *vec)
freq = [0] * n
inside = 0
left, right = xMin, xMin - 1
bestLeft, bestRight = xMin, xMax
while right < xMax:
right += 1
if right in indices:
for x in indices[right]:
freq[x] += 1
if freq[x] == 1:
inside += 1
while inside == n:
if right - left < bestRight - bestLeft:
bestLeft, bestRight = left, right
if left in indices:
for x in indices[left]:
freq[x] -= 1
if freq[x] == 0:
inside -= 1
left += 1
return [bestLeft, bestRight]
golang 解法, 执行用时: 40 ms, 内存消耗: 6.7 MB, 提交时间: 2023-05-16 11:25:37
var (
next []int
numsC [][]int
)
func smallestRange(nums [][]int) []int {
numsC = nums
rangeLeft, rangeRight := 0, math.MaxInt32
minRange := rangeRight - rangeLeft
max := math.MinInt32
size := len(nums)
next = make([]int, size)
h := &IHeap{}
heap.Init(h)
for i := 0; i < size; i++ {
heap.Push(h, i)
max = Max(max, nums[i][0])
}
for {
minIndex := heap.Pop(h).(int)
curRange := max - nums[minIndex][next[minIndex]]
if curRange < minRange {
minRange = curRange
rangeLeft, rangeRight = nums[minIndex][next[minIndex]], max
}
next[minIndex]++
if next[minIndex] == len(nums[minIndex]) {
break
}
heap.Push(h, minIndex)
max = Max(max, nums[minIndex][next[minIndex]])
}
return []int{rangeLeft, rangeRight}
}
type IHeap []int
func (h IHeap) Len() int { return len(h) }
func (h IHeap) Less(i, j int) bool { return numsC[h[i]][next[h[i]]] < numsC[h[j]][next[h[j]]] }
func (h IHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func Max(x, y int) int {
if x > y {
return x
}
return y
}
python3 解法, 执行用时: 136 ms, 内存消耗: 21.4 MB, 提交时间: 2023-05-16 11:25:21
# 贪心+最小堆
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
rangeLeft, rangeRight = -10**9, 10**9
maxValue = max(vec[0] for vec in nums)
priorityQueue = [(vec[0], i, 0) for i, vec in enumerate(nums)]
heapq.heapify(priorityQueue)
while True:
minValue, row, idx = heapq.heappop(priorityQueue)
if maxValue - minValue < rangeRight - rangeLeft:
rangeLeft, rangeRight = minValue, maxValue
if idx == len(nums[row]) - 1:
break
maxValue = max(maxValue, nums[row][idx + 1])
heapq.heappush(priorityQueue, (nums[row][idx + 1], row, idx + 1))
return [rangeLeft, rangeRight]
cpp 解法, 执行用时: 68 ms, 内存消耗: 14.2 MB, 提交时间: 2023-05-16 11:24:35
class Solution {
typedef pair<int, pair<int, int>> PII;
public:
vector<int> smallestRange(vector<vector<int>> &nums) {
int n = nums.size();
priority_queue<PII, vector<PII>, greater<PII>> pq;
int mx = -1e7, st = -1e7, ed = 1e7;
for (int i = 0; i < n; ++i) {
pq.push(make_pair(nums[i][0], make_pair(i, 0)));
mx = max(mx, nums[i][0]);
}
while (pq.size() == n) {
PII a = pq.top();
pq.pop();
int val = a.first, i = a.second.first, j = a.second.second;
if (mx - val < ed - st) st = val, ed = mx;
if (j + 1 < nums[i].size()) pq.push(make_pair(nums[i][j + 1], make_pair(i, j + 1))),mx = max(mx,nums[i][j+1]);
}
return {st, ed};
}
};
python3 解法, 执行用时: 280 ms, 内存消耗: 21.3 MB, 提交时间: 2023-05-16 11:24:20
# 合并k个排序链表，只要每次更新区间长度即可
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
from queue import PriorityQueue
q = PriorityQueue()
N = len(nums)
INF = 10 ** 9
maxv = -INF
start, end = -INF, INF
for i in range(N):
q.put((nums[i][0], i, 0))
maxv = max(maxv, nums[i][0])
while q.qsize() == N:
v, i, j= q.get()
if maxv - v < end - start:
start, end = v, maxv
if j + 1 < len(nums[i]):
nv = nums[i][j + 1]
q.put((nv, i, j + 1))
maxv = max(maxv, nv)
return [start, end]