两个有序数组间相加和的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中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到