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.
For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.
import collections
class Solution(object):
def smallestRange(self, nums):
"""
:type nums: List[List[int]]
:rtype: List[int]
"""
m=len(nums)
if m==0:
return []
self.dict=collections.defaultdict(list)
all_num=[]
for i,tmp_list in enumerate(nums):
for item in tmp_list:
self.dict[item].append(i)
all_num.append(item)
all_num.sort()
range_count=99999999
k=0
result=[]
k0=k
record_set={}
#print(all_num)
while k<len(all_num) and k0<len(all_num):
#k0=k
while len(record_set)!=m and k0<len(all_num) and k<=k0:
value=all_num[k0]
tmp_from_list=self.dict[value]
for item in tmp_from_list:
if item not in record_set.keys():
record_set[item]=1
else:
record_set[item]+=1
if len(record_set)==m:
break
k0+=1
if len(record_set)==m:
now_range=all_num[k0]-all_num[k]
if now_range<range_count:
range_count=now_range
result=[all_num[k],all_num[k0]]
tmp_from_list=self.dict[all_num[k]]
for item in tmp_from_list:
if item in record_set.keys():
record_set[item]-=1
if record_set[item]==0:
del record_set[item]
if len(record_set)!=m:
k0=k0+1
#print('k %d k0 %d all length %d'%(k,k0,len(all_num)))
#print(record_set)
k=k+1
return result
Always report time error, actually I don't know why. Solution code:
def smallestRange(self, nums):
k = len(nums)
if k == 1:
return [nums[0][0], nums[0][0]]
hashmap = {} # element in nums -> index of sublist
for i in range(k):
for ele in nums[i]:
if ele not in hashmap:
hashmap[ele] = set()
hashmap[ele].add(i)
array = sorted(hashmap)
l, r = 0, 0
slidingwindow = {}
ans = []
while r < len(array):
right = array[r]
for index in hashmap[right]:
if index not in slidingwindow:
slidingwindow[index] = 0
slidingwindow[index] += 1
while len(slidingwindow) == k:
left = array[l]
if not ans or right-left < ans[1]-ans[0] or right-left == ans[1]-ans[0] and left < ans[0]:
ans = [left, right]
for index in hashmap[left]:
slidingwindow[index] -= 1
if not slidingwindow[index]:
del slidingwindow[index]
l += 1
r += 1
return ans