难度: Medium
Submission
运行时间: 463 ms
内存: 107.9 MB
"""
bucket sort solution O(MN): find the distance of all combinations, and put them into bucket based on their distance.
In this way, the distances are represented by idx, which were sort by nature.
Since the range of distance is [0, 2000] which is much lower than the # of pairs, which is 1e6.
It's a good time to use bucket sort. Basically, it's to put each pair into the bucket representing its distance.
Eventually, we can loop thru each bucket from lower distance.
"""
"""
Among the available bikes and workers, we choose the (worker, bike) pair with the shortest Manhattan distance between each other, and assign the bike to that worker.
"""
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
m, n = len(workers), len(bikes)
# idx is distance, val is a list of (worker, bike) that have that distance
buckets = [[] for _ in range(2000)] # the bucket size is the max_possible_distance
for w_idx, w in enumerate(workers):
for b_idx, b in enumerate(bikes):
dist = abs(w[0] - b[0]) + abs(w[1] - b[1])
buckets[dist].append((w_idx, b_idx))
res = [-1] * m
used = set() # used bike
for dist_lst in buckets: # everytime, we deal with the smallest dist, by looping thru idx/dist
for w_idx, b_idx in dist_lst:
if res[w_idx] != -1 or b_idx in used: # if worker is assigned or bike is assigned
continue
res[w_idx] = b_idx
used.add(b_idx)
return res
# TC O(MN + K). Generating all the (worker, bike) pairs takes O(NM) time.
# Space complexity: O(NM + K)
# class Solution:
# def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
# heap = []
# m, n = len(workers), len(bikes)
# visited = set() # used bike
# res = [-1] * m
# # step 1: build the distance table
# dis = [[-1] * n for _ in range(m)]
# for i, (w0, w1) in enumerate(workers):
# for j, (b0, b1) in enumerate(bikes):
# tmp = abs(b0 - w0) + abs(b1 -w1)
# dis[i][j] = [tmp, j]
# for i in range(len(dis)): # for each work, rank in the order of the closest bike. the j won't be in the original order
# dis[i] = sorted(dis[i])
# # the shortest dis for all workers (w/o bike limitation)
# for i in range(m):
# heapq.heappush(heap, (dis[i][0][0], i, 0))
# count = 0
# while heap:
# _, i, j = heapq.heappop(heap)
# bike_id = dis[i][j][1]
# if res[i] == -1 and bike_id not in visited:
# res[i] = bike_id
# visited.add(bike_id)
# count += 1
# if count == m:
# return res
# elif res[i] == -1 and bike_id in visited:
# if j + 1 < n:
# heapq.heappush(heap, (dis[i][j +1][0], i, j +1))
Explain
这个题解采用了桶排序的策略（bucket sort）来处理校园自行车分配问题。首先计算每个工人到每辆自行车的曼哈顿距离，并将每对(工人, 自行车)根据距离分到不同的桶中。因为最大可能距离为2000，所以桶的数量也是2000。在所有距离计算完并分桶之后，按距离从小到大的顺序（即桶的顺序）来分配自行车给工人。如果一个工人已经分配了自行车或一个自行车已经被分配，就跳过，直到所有工人都被分配自行车。
时间复杂度: O(MN)
空间复杂度: O(MN)
"""
# Bucket sort solution for assigning bikes to workers based on the shortest Manhattan distance.
# This approach uses a bucket sort mechanism where each bucket corresponds to a specific distance,
# and each bucket contains list of (worker_index, bike_index) pairs with that distance.
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
m, n = len(workers), len(bikes) # Number of workers and bikes
# Initialize buckets for each possible distance (up to 2000)
buckets = [[] for _ in range(2000)]
# Populate buckets with (worker, bike) pairs based on their Manhattan distance
for w_idx, w in enumerate(workers):
for b_idx, b in enumerate(bikes):
dist = abs(w[0] - b[0]) + abs(w[1] - b[1]) # Compute Manhattan distance
buckets[dist].append((w_idx, b_idx))
res = [-1] * m # Result list to store the assigned bike index for each worker
used = set() # Set to keep track of assigned bikes
# Process each bucket in order of increasing distance
for dist_lst in buckets:
for w_idx, b_idx in dist_lst:
if res[w_idx] != -1 or b_idx in used: # Skip if worker or bike already assigned
continue
res[w_idx] = b_idx # Assign bike to worker
used.add(b_idx) # Mark bike as used
return res
"""
Explore
桶排序在处理自行车分配问题时具有显著的优势，因为它能高效地处理按距离排序的需求。桶排序的时间复杂度为O(n)，在距离的最大范围已知且有限（如2000）的情况下，这种排序方法比其他常规的排序算法（如快速排序、归并排序等O(n log n)的算法）更为高效。此外，桶排序能够直接根据距离将工人和自行车的对应关系分类到不同的桶中，这使得实现按照距离优先的分配策略变得直接和简单。
在桶排序的具体实现中，每个桶代表一种特定的曼哈顿距离，桶中存储了所有该距离下的工人和自行车的配对关系。算法从距离最小的桶开始处理，依次检查每个桶中的配对关系。对于每对工人和自行车，如果该工人未被分配自行车且该自行车未被分配，则将此自行车分配给该工人，并标记此自行车为已用。这种方式确保了每个工人都被优先分配到距离最近的自行车，因为一旦工人被分配了自行车，就不会再考虑其他更远距离的自行车。
最大可能的曼哈顿距离是基于坐标平面上两点之间的距离计算得出的。假设坐标的取值范围是0到1000，曼哈顿距离是两点之间在x轴和y轴方向上差的绝对值之和。因此，两点的最大曼哈顿距离发生在一点在坐标原点（0,0），另一点在（1000,1000）时，此时距离为1000+1000=2000。这是在坐标范围最大化的情况下计算出的最大可能曼哈顿距离。
当多对工人和自行车具有相同的最小曼哈顿距离时，题解中的算法按照它们在输入列表中的顺序来决定分配顺序。具体来说，算法先遍历所有工人，对于每个工人按照自行车列表的顺序计算距离并将对应的配对关系添加到相应的桶中。因此，如果存在相同距离的多个配对关系，它们在桶中的顺序反映了它们在原始列表中的相对顺序。在分配时，算法也会遵循这个顺序，从而保持一种稳定的分配顺序。