Given two object arrays of 'id, weight' (sorted by weight), merge them together and create a one single array. If the 'id's are same, values should be added up and only keep one left. Final result should still be sorted by weight.
有一个对象，含有id和weight两种属性，现在有两个这种对象的数组，分别按照重量排序，要求合并，然后相同的id重量应该加起来只保留一个。要求最后的结果也是按照重量排序的。
1. 询问
id和weight是什么类型？假设id是字符串，weight是整型。
weight有没有可能小于0？假设weight总是大于等于0.
题里的排序是指升序还是降序？假设是升序。
原本的一个数组里面有没有可能存在相同id的两个对象？假设给出的单个数组不会有相同id的对象。
2. 分析
直观解法
这个题让人很容易联想到归并排序，不同的是有两个属性需要考虑，所以多了一步相同id的合并。
就这道题而言，看上去只有两种可能，一个是归并之前合并id，另一个就是归并之后合并id。
归并之前合并id
假如归并之前合并id，先建立以id为键值的哈希表，把一个数组放进去，以index和weight作为value，然后可以遍历另一个数组。只是数组里面的删除并不是那么方便，合并之后的数也只能再另起一个数组然后不断插入。因为删除操作效率太低，考虑置-1，但是插入就没办法回避了。最坏情况时，两个数组都是一样的id，因为插入是O(n)，那么整体效率O(n^2)，不够高。
归并之后合并id
假设两个数组长度分别为m和n，那么归并就是O(m+n)。然后，还是放进哈希表里面，{id:[index, weight]}，遍历数组，假如找到有重复的id，weight相加，留下一个，另一个置-1，复杂度O(m+n)。最后再按照weight排序，把前面-1的部分舍弃即可。这一步O((m+n)log(m+n))。总体时间复杂度O((m+n)log(m+n))，空间复杂度O(m+n)。
3. 代码
class object:
def __init__(self, id, w):
self.w = w
self.id = id
def __repr__(self):
return self.id + ":" + str(self.w)
class Solution:
def mergeObjects(self, l1, l2):
if not l1 or not l2:
return l1 or l2
ret = []
i = j = 0
# merge
while i < len(l1) and j < len(l2):
if l1[i].w <= l2[j].w:
ret.append(l1[i])
i += 1
else:
ret.append(l2[j])
j += 1
while i < len(l1):
ret.append(l1[i])
i += 1
while j < len(l2):
ret.append(l2[j])
j += 1
# put into dict and handle replicate id
d = {}
for i, ob in enumerate(ret):
if ob.id not in d:
d[ob.id] = [i, ob.w]
else:
prev_idx = d[ob.id][0]
prev_w = d[ob.id][1]
ret[prev_idx].w = -1
ret[i].w += prev_w
del d[ob.id]
# sort by weight
ret.sort(key=lambda x: x.w)
# remove -1
return filter(lambda x: x.w != -1, ret)
4. 总结
难度medium。
