leetcode 632. Smallest Range k个数组至少一个元素最小区间+典型移动窗口做法

发布于:2021-09-28 12:23:20

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
-105 <= value of elements <= 105.


本题题意很简单,虽然是分开的k个list,但是可以合并到一起,然后做排序,使用移动窗口去做即可


按照k个链表做分类,然后使用map做计数,然后移动窗口,不断收缩窗口即可,很棒的题


本质上和本题leetcode 76. Minimum Window Substring 双指针 + Map + 移动窗口 是一样的做法


这道题十分的棒,很值得学*


代码如下:


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;



class Solution
{
public:
vector smallestRange(vector>& nums)
{
vector> all;
int kind = nums.size();
for (int i = 0; i < kind; i++)
{
for (int a : nums[i])
all.push_back(make_pair(a, i));
}
sort(all.begin(), all.end());

map mmp;
vector res = {INT_MAX,INT_MAX};
int left = 0, count = 0 , minDiff = INT_MAX;
for (int right = 0; right < all.size(); right++)
{
mmp[all[right].second] += 1;
if(mmp[all[right].second] == 1)
count++;

while (count == kind && left <= right)
{
int diff = all[right].first - all[left].first;
if (diff < minDiff)
{
minDiff = diff;
res = { all[left].first , all[right].first};
}
else if (diff == minDiff && all[left].first < res[0])
res = { all[left].first , all[right].first };

mmp[all[left].second] -= 1;
if (mmp[all[left].second] == 0)
count--;
left++;
}
}
return res;
}
};

相关推荐

最新更新

猜你喜欢