每日力扣终于来到了第90天。
今天挑战的题目叫“Smallest Range Covering Elements from K Lists”,中文名竟然就叫“最小区间”,这翻译简直太偷懒了。
这虽然是一道困难题,却没有特别困难的点,而是一些列技巧的组合运用。
这道题用到了结构体排序、双指针滑动窗口、哈希表计数。
我们先进行排序,排序所有的数字,但问题是会丢失该数所在的组号,因此我们需要使用结构体。
每个组的数字至少用一个,那么我们滑动窗口的条件很简单就有了。
当每组中有的组的数量在窗口中不足1,我们就向右扩大窗口。
当所有组的数量都大于等于1,我们就向右缩小窗口。
那么怎么来计数呢,可以使用数组,也可以使用哈希表。
做这道题的时候,要注意不能犯两个错误。
缩小窗口应该也是向右,所以left应该去++。不要错误写成–。
还有滑动窗口都从下标0开始的话,那么下标0的数据应该提前放入哈希表。