标签:
难度: Easy
标签:
难度: Easy
运行时间: 69 ms
内存: 16.4 MB
import heapq class Solution: def supplyWagon(self, supplies: List[int]) -> List[int]: # m = {} # for i in range(len(supplies)): # m[i] = supplies[i] # def findNext(m, i, l): # r = i + 1 # while r < l and r not in m: # r += 1 # return r # l = len(supplies) # bound = l # while l != (len(supplies) >> 1): # i1 = 0 # i2 = 0 # r1 = 0 # r2 = 0 # ma = 100000 # while i1 != bound - 1: # i2 = findNext(m, i1, bound) # if m[i1] + m[i2] < ma: # ma = m[i1] + m[i2] # r1 = i1 # r2 = i2 # i1 = i2 # m[r1] += m[r2] # del m[r2] # if r2 == bound - 1: # bound = r1 + 1 # l -= 1 # arr = [] # for i, j in m.items(): # arr.append([i,j]) # arr.sort(key=lambda x:x[0]) # r = [x[1] for x in arr] # return r def findPrev(supplies, i): i -= 1 while i >= 0 and supplies[i] == -1: i -= 1 return i def findNext(supplies, i): i += 1 while i < len(supplies) and supplies[i] == -1: i += 1 return i arr = [[supplies[i] + supplies[i + 1], i, i + 1] for i in range(len(supplies) - 1)] heapq.heapify(arr) l = (len(supplies) + 1) >> 1 i = 0 while i < l: t = heapq.heappop(arr) while supplies[t[1]] + supplies[t[2]] != t[0]: t = heapq.heappop(arr) supplies[t[1]] += supplies[t[2]] supplies[t[2]] = -1 prev = findPrev(supplies, t[1]) next = findNext(supplies, t[2]) if prev != -1: heapq.heappush(arr, [supplies[prev] + supplies[t[1]], prev, t[1]]) if next != len(supplies): heapq.heappush(arr, [supplies[next] + supplies[t[1]], t[1], next]) i += 1 r = [] for s in supplies: if s != -1: r.append(s) return r
该题解采用了堆(heap)数据结构来优化寻找最小相邻马车对的过程。首先,创建一个列表,列表中的每个元素是一个包含两个相邻马车物资之和和它们的索引的元组。然后将这个列表转为一个堆结构,以便快速获取最小元素。在每次合并过程中,从堆中弹出最小元素(即物资之和最小的两个相邻马车),然后进行合并操作。合并后,需要更新相关的马车对信息并重新加入堆中以保持堆的性质。合并过程持续进行直到车队长度减半。在整个过程中,使用-1标记已合并的马车,以便在计算过程中跳过它们。
时间复杂度: O(n log n)
空间复杂度: O(n)
import heapq class Solution: def supplyWagon(self, supplies: List[int]) -> List[int]: # Helper function to find the previous non-merged wagon def findPrev(supplies, i): i -= 1 while i >= 0 and supplies[i] == -1: i -= 1 return i # Helper function to find the next non-merged wagon def findNext(supplies, i): i += 1 while i < len(supplies) and supplies[i] == -1: i += 1 return i # Initialize the min-heap with the sum of every two adjacent wagons arr = [[supplies[i] + supplies[i + 1], i, i + 1] for i in range(len(supplies) - 1)] heapq.heapify(arr) # Calculate the target length after all merges l = (len(supplies) + 1) >> 1 i = 0 while i < l: # Get the smallest pair from the heap t = heapq.heappop(arr) # Check if the pair is still valid while supplies[t[1]] + supplies[t[2]] != t[0]: t = heapq.heappop(arr) # Merge the two wagons supplies[t[1]] += supplies[t[2]] supplies[t[2]] = -1 # Update the heap with new possible pairs prev = findPrev(supplies, t[1]) next = findNext(supplies, t[2]) if prev != -1: heapq.heappush(arr, [supplies[prev] + supplies[t[1]], prev, t[1]]) if next != len(supplies): heapq.heappush(arr, [supplies[next] + supplies[t[1]], t[1], next]) i += 1 # Collect non-merged wagons for the result r = [] for s in supplies: if s != -1: r.append(s) return r
在解决方案中,每次从堆中取出元素后,都会进行验证以确保这些马车未被合并,并且它们的物资之和仍然是最新的。验证过程中,如果发现取出的马车对的物资之和已经变化(可能由于其中一个马车已经与其他马车合并),则继续从堆中取出下一个元素,并进行同样的验证。这个过程一直持续到找到一个有效的、当前最小的相邻马车对。这种办法通过循环验证来确保每次处理的马车对都是当前未合并车队中的最小对。
合并过程中,当发现一个已经合并的马车紧邻另一对需要合并的马车时,解决方案中使用了两个辅助函数(findPrev和findNext)来找到任一马车左边或右边最近的未合并马车。这样,在每次合并后,通过这些辅助函数更新相邻的马车对,并将这些新的马车对重新加入堆中。这确保了数据的准确性,避免了因已合并的马车对干扰合并逻辑从而引发错误。
使用-1标记已合并的马车是一种常见的方法来标识某些元素不应被进一步处理。在本程序中,如果没有正确使用辅助函数findPrev和findNext来找到有效的未合并马车,可能会导致重复计算或错误跳过。例如,如果直接访问数组中的前一个或下一个元素而没有检查它是否标记为-1,就可能错误地对已合并的马车进行操作。因此,正确地实现和使用这些辅助函数是确保程序准确性的关键。