华为OD E卷（100分）25-整数对最小和

前言

工作了十几年，从普通的研发工程师一路成长为研发经理、研发总监。临近40岁，本想辞职后换一个相对稳定的工作环境一直干到老, 没想到离职后三个多月了还没找到工作，愁肠百结。为了让自己有点事情做，也算提高一下自己的编程能力，无聊之余打算用一些大厂的编程题练练手。希望通过这些分享能够帮到一些人，也希望能和看到此文的大神们沟通交流，提升自己，更希望在此期间能够找到一份理想的工作。

题目描述

给定两个整数数组array1、array2，数组元素按升序排列。

假设从array1、array2中分别取出一个元素可构成一对元素，现在需要取出k对元素，并对取出的所有元素求和，计算和的最小值。

注意：

两对元素如果对应于array1、array2中的两个下标均相同，则视为同一对元素。

输入

输入两行数组array1、array2，每行首个数字为数组大小size(0 < size <= 100);

0 < array1[i] <= 1000

0 < array2[i] <= 1000

接下来一行为正整数k

0 < k <= array1.size() * array2.size()

输出

满足要求的最小和。

示例

输入
3 1 1 2
3 1 2 3
2

输出
4

说明

用例中，需要取2对元素

取第一个数组第0个元素与第二个数组第0个元素组成1对元素[1,1];

取第一个数组第1个元素与第二个数组第0个元素组成1对元素[1,1];

求和为1+1+1+1=4，为满足要求的最小和。

解题思路

1、暴力枚举法：

双重循环遍历array1和array2的所有元素对，记录它们的和。
将所有可能的和排序，取前K个和的最小值。
但这种方法的时间复杂度较高，为O(n^2 log(n^2))，其中n为数组的大小。

2、最小堆优化：

初始时，将array1的第一个元素与array2的所有元素配对，并将这些配对的和以及对应的array1和array2的下标插入最小堆中。
每次从堆中取出和最小的元素对，将其和加入答案中，并将该元素对对应的array1的下一个元素与array2的当前元素（或下一个未使用的元素）组合并插入堆中。
重复上述步骤，直到从堆中取出了K个元素对。
这种方法的时间复杂度较低，为O(k log n)，其中n为数组的大小，且空间复杂度也相对较低。

题解

Java实现

package huawei.e100;import java.util.PriorityQueue;
import java.util.Scanner;/**
* @author arnold
* @date 2024年12月17日
* 
*/
public class T25 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()) {//array1int m = sc.nextInt();int[] array1 = new int[m];for (int i = 0; i < m; i++) {array1[i] = sc.nextInt();}// array2int n = sc.nextInt();int[] array2 = new int[n];for (int i = 0; i < n; i++) {array2[i] = sc.nextInt();}// 读取kint k = sc.nextInt();int sum = run(array1, array2, k);System.out.println(sum);}}//暴力枚举法static int run(int[] array1, int[] array2, int k) {PriorityQueue<Integer> data = new PriorityQueue<>((a,b) -> a-b);for (int i = 0; i < array1.length && i < k; i++) {for (int j = 0; j < array2.length && j < k; j++) {data.add(array1[i] + array2[j]);}}int sum = 0;while(k > 0) {sum += data.poll();k--;}return sum;}// 最小堆化方法public static int run2(int[] array1, int[] array2, int k) {PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);// 初始化最小堆，将array1的第一个元素与array2的所有元素配对并插入堆中for (int j = 0; j < array2.length && j < k; j++) {queue.offer(new int[]{array1[0] + array2[j], 0, j});}int sum = 0;while (k > 0) {int[] pair = queue.poll();assert pair != null;sum += pair[0];int i = pair[1];int j = pair[2];// 如果array1还有剩余元素，则将下一个元素与array2的当前元素配对并插入堆中if (i + 1 < array1.length) {queue.offer(new int[]{array1[i + 1] + array2[j], i + 1, j});}k--;}return sum;}}