632. Smallest Range Covering Elements from K Lists #
题目 #
You have k lists of sorted integers in ascending 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: [[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].
Note:
- The given list may contain duplicates, so ascending order means >= here.
- 1 <=
k<= 3500 - -10^5 <=
value of elements<= 10^5.
题目大意 #
你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
注意:
- 给定的列表可能包含重复元素，所以在这里升序表示 >= 。
- 1 <= k <= 3500
- -105 <= 元素的值 <= 105
- 对于使用Java的用户，请注意传入类型已修改为List<List
>。重置代码模板后可以看到这项改动。
解题思路 #
- 给出 K 个数组，要求在这 K 个数组中找到一个区间，至少能包含这 K 个数组中每个数组中的一个元素。
- 这一题是第 76 题的变种版。第 76 题是用滑动窗口来解答的，它要求在母字符串 S 中找到最小的子串能包含 T 串的所有字母。这一题类似的，可以把母字符串看成 K 个数组合并起来的大数组，那么 T 串是由 K 个数组中每个数组中抽一个元素出来组成的。求的区间相同，都是能包含 T 的最小区间。另外一个区别在于，第 76 题里面都是字符串，这一题都是数字，在最终拼接成 T 串的时候需要保证 K 个数组中每个都有一个元素，所以理所当然的想到需要维护每个元素所在数组编号。经过上述的转换，可以把这道题转换成第 76 题的解法了。
- 在具体解题过程中，用 map 来维护窗口内 K 个数组出现的频次。时间复杂度 O(n*log n)，空间复杂度是O(n)。
代码 #
package leetcode
import (
"math"
"sort"
)
func smallestRange(nums [][]int) []int {
numList, left, right, count, freqMap, res, length := []element{}, 0, -1, 0, map[int]int{}, make([]int, 2), math.MaxInt64
for i, ns := range nums {
for _, v := range ns {
numList = append(numList, element{val: v, index: i})
}
}
sort.Sort(SortByVal{numList})
for left < len(numList) {
if right+1 < len(numList) && count < len(nums) {
right++
if freqMap[numList[right].index] == 0 {
count++
}
freqMap[numList[right].index]++
} else {
if count == len(nums) {
if numList[right].val-numList[left].val < length {
length = numList[right].val - numList[left].val
res[0] = numList[left].val
res[1] = numList[right].val
}
}
freqMap[numList[left].index]--
if freqMap[numList[left].index] == 0 {
count--
}
left++
}
}
return res
}
type element struct {
val int
index int
}
type elements []element
// Len define
func (p elements) Len() int { return len(p) }
// Swap define
func (p elements) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
// SortByVal define
type SortByVal struct{ elements }
// Less define
func (p SortByVal) Less(i, j int) bool {
return p.elements[i].val < p.elements[j].val
}