Leetcode-3479.-Fruits-Into-Baskets-III
目录
Leetcode 3479. Fruits Into Baskets III
题目链接：
1. 解题思路
这一题思路本质上就是考察每一个水果被考察时找到第一个满足条件且未被使用的basket。
因此，我们只需要将basket按照其capacity进行排序，此时，考察每一个水果时，我们用二分法即可快速找到某一个坐标idx满足其后任意一个箱子都可以用于盛放该水果。此时，我们就要从对应的这些篮子当中找到其原始的坐标最小的位置即可。而这就是一个典型的segment tree的问题了。
对于segment tree，网上已经有不少相关的介绍了，我自己也写过一篇小文章作为备忘（ ），因此这里就不过多展开了，有兴趣的读者可以自行去了解一下。
2. 代码实现
给出python代码实现如下：
class SegmentTree:
def __init__(self, arr):
self.length = len(arr)
self.tree = self.build(arr)
def feature_func(self, *args):
return min(args)
def build(self, arr):
n = len(arr)
tree = [0 for _ in range(2*n)]
for i in range(n):
tree[i+n] = arr[i]
for i in range(n-1, 0, -1):
tree[i] = self.feature_func(tree[2*i], tree[2*i+1])
return tree
def update(self, idx, val):
idx = idx + self.length
self.tree[idx] = val
while idx > 1:
self.tree[idx // 2] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])
idx = idx // 2
return
def query(self, lb, rb):
lb += self.length
rb += self.length
nodes = []
while lb < rb:
if lb % 2 == 1:
nodes.append(self.tree[lb])
lb += 1
if rb % 2 == 0:
nodes.append(self.tree[rb])
rb -= 1
lb = lb // 2
rb = rb // 2
if lb == rb:
nodes.append(self.tree[rb])
return self.feature_func(*nodes)
class Solution:
def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
n = len(fruits)
ordered_baskets = sorted([(cap, idx) for idx, cap in enumerate(baskets)])
ordered_baskets_capacity = [x[0] for x in ordered_baskets]
ordered_baskets_index = [x[1] for x in ordered_baskets]
segment_tree = SegmentTree(ordered_baskets_index)
ans = 0
for fruit in fruits:
idx = bisect.bisect_left(ordered_baskets_capacity, fruit)
if idx >= n:
ans += 1
continue
left_most_avaliable = segment_tree.query(idx, n-1)
if left_most_avaliable >= n:
ans += 1
continue
basket = (baskets[left_most_avaliable], left_most_avaliable)
idx = bisect.bisect_left(ordered_baskets, basket)
segment_tree.update(idx, n)
return ans提交代码评测得到：耗时2398ms，占用内存43.9MB。