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] 按非递减顺序排列
原站题解
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]