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<Integer>>。重置代码模板后可以看到这项改动。

解题思路

给出 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
}