0632. Smallest Range Covering Elements From K Lists

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:

  1. The given list may contain duplicates, so ascending order means >= here.
  2. 1 <= k <= 3500
  3. -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
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者