No.0007-CareerCup

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。