首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >两有序数组间相加的TOPK问题

两有序数组间相加的TOPK问题

作者头像
你的益达
发布2020-08-24 12:46:22
1.2K0
发布2020-08-24 12:46:22
举报

给定两有序数组arr1和arr2,以及整数k,返回来自arr1和arr2两个数相加和最大的前k个,此外两数必须来自不同的数组。

示例:
arr1 = [1 2 3 4 5]
arr2 = [3 5 7 9 11]
k = 4
输出
[16 15 14 14]
要求时间复杂度为O(klog(k))

解决方案:

我们发现最大的元素为arr1[M - 1] 与 arr2[N - 1]之和,比起稍小的两组数据分别为arr1[M - 1] + arr2[N - 2]和arr1[M - 2] + arr2[N - 1]。

定义一大根堆,初始将arr1[M - 1] + arr2[N - 1]存入堆中。

然后使用bfs,每次从堆中弹出最大值元素记做(i, j),并将其的(i - 1, j) 和 (i , j - 1)入堆。如此弹出k个元素即可。

public class Main{
     public static class Node{
         int x;
         int y;
         public Node(int x, int y) {
             this.x = x;
             this.y = y;
         }
     }
     public static int[][] directs = {{0, -1}, {-1, 0}};
     public static List<Integer>selution(int[] arr1, int[] arr2, int k) {
         Queue<Node> maxHeap = new PriorityQueue<>(new Comparator<Node>() {
             public int compare(Node node1, Node node2) {
                 return (arr1[node2.x] + arr2[node2.y]) - (arr1[node1.x] + arr2[node1.y]); 
             }
         });
         List<Integer> ans = new ArrayList<>(k);
         int M = arr1.length;
         int N = arr2.length;
         boolean[][] visted = new boolean[M][N];
         maxHeap.add(new Node(M - 1, N - 1));
         visted[M - 1][N - 1] = true;
         for(int i = 0; i < k; i++) {
             Node cur = maxHeap.remove();
             ans.add(arr1[cur.x] + arr2[cur.y]);
             for(int[] direct : directs) {
                 int x = cur.x + direct[0];
                 int y = cur.y + direct[1];
                 if(x < 0 || y < 0 || visted[x][y]) {
                     continue;
                 }
                 maxHeap.add(new Node(x, y));
             }

         }
         return ans;

     }
}

document.querySelectorAll('.github-emoji') .forEach(el => { if (!el.dataset.src) { return; } const img = document.createElement('img'); img.style = 'display:none !important;'; img.src = el.dataset.src; img.addEventListener('error', () => { img.remove(); el.style.color = 'inherit'; el.style.backgroundImage = 'none'; el.style.background = 'none'; }); img.addEventListener('load', () => { img.remove(); }); document.body.appendChild(img); });

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-08-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解决方案:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档