题解 | #反转链表#

两个有序数组间相加和的Topk问题

http://www.nowcoder.com/practice/7201cacf73e7495aa5f88b223bbbf6d1

两个有序数组间相加和的Topk问题；优先队列、最大堆。

取自：https://blog.csdn.net/weixin_44503157/article/details/117962906

一、思路

用最大堆来实现。然后再加上用个bfs来扫描周围的最大值。

即：

将右下角唯一知道的最大值压入最大堆；
弹出最大堆中最大的值，这个值就可以加入最终结果中；
将这个最大值的左边节点和上边节点加入最大堆中。
继续步骤2.的操作。直到压入了k个答案。

二、难点：

1、标记地址

堆中数据弹出，虽然知道是最大的，但是并不知道其所在坐标。

需要自己定一个数据结构。其中包含了val，和其坐标x、y；

然后定义最大堆的时候，用这个数据结构的val来作为构建堆时比较的值。

我使用了stl中的优先队列，定义的时候，可以声明其比较函数。

2、去重

单纯的这样bfs 可能会进到重复的坐标中。使得一个坐标的值进入两次。

我用集合 set来标记对应坐标，防止一个坐标重复进堆。

三、代码

struct nodde {
    int val;
    int x;
    int y;
};
class mycomparison
{
public:
    bool operator() (const nodde& lhs, const nodde&rhs) const
    {
        return (lhs.val < rhs.val);
    }
};
vector<int> topK(vector<int> &arr1, vector<int>&arr2, int k)
{
    int cur1 = arr1.size() - 1, cur2 = arr2.size() - 1;
    priority_queue<nodde, std::vector<nodde>, mycomparison >
        my_heap;
    vector<int> result;
    nodde temp, temp1, temp2;
    temp.val = arr1[cur1] + arr2[cur2];
    unordered_set<string> my_set;
    temp.x = cur1;
    temp.y = cur2;
    my_heap.push(temp);
    my_set.insert(to_string(cur1)+","+to_string(cur2));
    int cnt = 0;
    while (cnt < k)
    {
        temp = my_heap.top();
        my_heap.pop();
        temp1.x = temp.x - 1;
        temp1.y = temp.y;
        // if(temp.x>=0&&temp1.y>=0)
        temp1.val = arr1[temp1.x] + arr2[temp1.y];
        temp2.x = temp.x;
        temp2.y = temp.y - 1;
        temp2.val = arr1[temp2.x] + arr2[temp2.y];

        result.push_back(temp.val);

        if(my_set.count(to_string(temp1.x)+","+to_string(temp1.y)) ==0)
        {
            my_heap.push(temp1);
            my_set.insert(to_string(temp1.x)+","+to_string(temp1.y));
        }

        if(my_set.count(to_string(temp2.x)+","+to_string(temp2.y)) ==0)
        {
            my_heap.push(temp2);
            my_set.insert(to_string(temp2.x)+","+to_string(temp2.y));
        }

        cnt++;


    }

    return result;
}