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

2024-06-21 21:48

本文主要是介绍两个有序数组间相加和的Top k问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这里写图片描述

import java.util.*;
//两个有序数组间相加和的Top k问题
public class FindArrTopK{//堆节点的定义public static class HeapNode{public int row;public int col;public int value;public HeapNode(int row,int col,int value){this.row=row;this.col=col;this.value=value;}}//获得top k问题public static int[] topKSum(int[] a1, int[] a2, int topK) {if (a1 == null || a2 == null || topK < 1) {return null;}topK = Math.min(topK, a1.length * a2.length);HeapNode[] heap = new HeapNode[topK + 1];int heapSize = 0;int headR = a1.length - 1;int headC = a2.length - 1;int uR = -1;int uC = -1;int lR = -1;int lC = -1;heapInsert(heap, heapSize++, headR, headC, a1[headR] + a2[headC]);HashSet<String> positionSet = new HashSet<String>();int[] res = new int[topK];int resIndex = 0;while (resIndex != topK) {HeapNode head = popHead(heap, heapSize--);res[resIndex++] = head.value;headR = head.row;headC = head.col;uR = headR - 1;uC = headC;if (headR != 0 && !isContains(uR, uC, positionSet)) {heapInsert(heap, heapSize++, uR, uC, a1[uR] + a2[uC]);addPositionToSet(uR, uC, positionSet);}lR = headR;lC = headC - 1;if (headC != 0 && !isContains(lR, lC, positionSet)) {heapInsert(heap, heapSize++, lR, lC, a1[lR] + a2[lC]);addPositionToSet(lR, lC, positionSet);}}return res;}public static HeapNode popHead(HeapNode[] heap, int heapSize) {HeapNode res = heap[0];swap(heap, 0, heapSize - 1);heap[--heapSize] = null;heapify(heap, 0, heapSize);return res;}public static void heapify(HeapNode[] heap, int index, int heapSize) {int left = index * 2 + 1;int right = index * 2 + 2;int largest = index;while (left < heapSize) {if (heap[left].value > heap[index].value) {largest = left;}if (right < heapSize && heap[right].value > heap[largest].value) {largest = right;}if (largest != index) {swap(heap, largest, index);} else {break;}index = largest;left = index * 2 + 1;right = index * 2 + 2;}}public static void heapInsert(HeapNode[] heap, int index, int row, int col,int value) {heap[index] = new HeapNode(row, col, value);int parent = (index - 1) / 2;while (index != 0) {if (heap[index].value > heap[parent].value) {swap(heap, parent, index);index = parent;parent = (index - 1) / 2;} else {break;}}}public static void swap(HeapNode[] heap, int index1, int index2) {HeapNode tmp = heap[index1];heap[index1] = heap[index2];heap[index2] = tmp;}public static boolean isContains(int row, int col, HashSet<String> set) {return set.contains(String.valueOf(row + "_" + col));}public static void addPositionToSet(int row, int col, HashSet<String> set) {set.add(String.valueOf(row + "_" + col));}// For test, this method is inefficient but absolutely rightpublic static int[] topKSumTest(int[] arr1, int[] arr2, int topK) {int[] all = new int[arr1.length * arr2.length];int index = 0;for (int i = 0; i != arr1.length; i++) {for (int j = 0; j != arr2.length; j++) {all[index++] = arr1[i] + arr2[j];}}Arrays.sort(all);int[] res = new int[Math.min(topK, all.length)];index = all.length - 1;for (int i = 0; i != res.length; i++) {res[i] = all[index--];}return res;}public static int[] generateRandomSortArray(int len) {int[] res = new int[len];for (int i = 0; i != res.length; i++) {res[i] = (int) (Math.random() * 50000) + 1;}Arrays.sort(res);return res;}public static boolean isEqual(int[] arr1, int[] arr2) {if (arr1 == null || arr2 == null || arr1.length != arr2.length) {return false;}for (int i = 0; i != arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}//打印数组public static void printArray(int[] arr) {for (int i = 0; i != arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[]args){//System.out.println("Hello");int[]arr1={1,2,3,4,5};int[]arr2={3,5,7,9,11};int k=4;int[]res = topKSum(arr1,arr2,k);printArray(res);}
}

这里写图片描述

这篇关于两个有序数组间相加和的Top k问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1082424

相关文章

线上Java OOM问题定位与解决方案超详细解析

《线上JavaOOM问题定位与解决方案超详细解析》OOM是JVM抛出的错误,表示内存分配失败,:本文主要介绍线上JavaOOM问题定位与解决方案的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一、OOM问题核心认知1.1 OOM定义与技术定位1.2 OOM常见类型及技术特征二、OOM问题定位工具

Vue3绑定props默认值问题

《Vue3绑定props默认值问题》使用Vue3的defineProps配合TypeScript的interface定义props类型,并通过withDefaults设置默认值,使组件能安全访问传入的... 目录前言步骤步骤1:使用 defineProps 定义 Props步骤2:设置默认值总结前言使用T

JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法

《JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法》:本文主要介绍JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法,每种方法结合实例代码给大家介绍的非常... 目录引言:为什么"相等"判断如此重要?方法1:使用some()+includes()(适合小数组)方法2

Web服务器-Nginx-高并发问题

《Web服务器-Nginx-高并发问题》Nginx通过事件驱动、I/O多路复用和异步非阻塞技术高效处理高并发,结合动静分离和限流策略,提升性能与稳定性... 目录前言一、架构1. 原生多进程架构2. 事件驱动模型3. IO多路复用4. 异步非阻塞 I/O5. Nginx高并发配置实战二、动静分离1. 职责2

解决升级JDK报错:module java.base does not“opens java.lang.reflect“to unnamed module问题

《解决升级JDK报错:modulejava.basedoesnot“opensjava.lang.reflect“tounnamedmodule问题》SpringBoot启动错误源于Jav... 目录问题描述原因分析解决方案总结问题描述启动sprintboot时报以下错误原因分析编程异js常是由Ja

MySQL 表空却 ibd 文件过大的问题及解决方法

《MySQL表空却ibd文件过大的问题及解决方法》本文给大家介绍MySQL表空却ibd文件过大的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考... 目录一、问题背景:表空却 “吃满” 磁盘的怪事二、问题复现:一步步编程还原异常场景1. 准备测试源表与数据

解决Nginx启动报错Job for nginx.service failed because the control process exited with error code问题

《解决Nginx启动报错Jobfornginx.servicefailedbecausethecontrolprocessexitedwitherrorcode问题》Nginx启... 目录一、报错如下二、解决原因三、解决方式总结一、报错如下Job for nginx.service failed bec

SysMain服务可以关吗? 解决SysMain服务导致的高CPU使用率问题

《SysMain服务可以关吗?解决SysMain服务导致的高CPU使用率问题》SysMain服务是超级预读取,该服务会记录您打开应用程序的模式,并预先将它们加载到内存中以节省时间,但它可能占用大量... 在使用电脑的过程中,CPU使用率居高不下是许多用户都遇到过的问题,其中名为SysMain的服务往往是罪魁

MySQ中出现幻读问题的解决过程

《MySQ中出现幻读问题的解决过程》文章解析MySQLInnoDB通过MVCC与间隙锁机制在可重复读隔离级别下解决幻读,确保事务一致性,同时指出性能影响及乐观锁等替代方案,帮助开发者优化数据库应用... 目录一、幻读的准确定义与核心特征幻读 vs 不可重复读二、mysql隔离级别深度解析各隔离级别的实现差异

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基