华为OD机试真题---整数对最小和

题目描述

给定两个整数数组array1和array2，数组元素按升序排列。假设从array1和array2中分别取出一个元素可构成一对元素。现在需要取出K个元素对（即从两个数组中各取一个元素组成一个对，共取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

解题思路

1. 暴力枚举法：

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

2. 双指针法结合贪心策略（优化方法）：

   • 利用数组的有序性，使用双指针从头开始遍历两个数组。
   • 每次选择两个指针指向的元素和中较小的一个，将其加入答案中，并将所在数组的指针向后移动一位。
   • 使用一个数据结构（如最小堆）来维护当前选取的元素对和以及对应的数组下标，以确保每次都能选择到和最小的元素对。
   • 但这种方法需要额外的空间来存储元素对和及其下标，且当K接近n^2时，算法效率可能较低。

3. 最小堆优化：

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

示例代码（最小堆优化）

import java.util.PriorityQueue;
import java.util.Scanner;

public class IntegerPairMinSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取array1
        int m = scanner.nextInt();
        int[] array1 = new int[m];
        for (int i = 0; i < m; i++) {
            array1[i] = scanner.nextInt();
        }

        // 读取array2
        int n = scanner.nextInt();
        int[] array2 = new int[n];
        for (int i = 0; i < n; i++) {
            array2[i] = scanner.nextInt();
        }

        // 读取k
        int k = scanner.nextInt();

        // 调用方法计算最小和
        System.out.println(findMinSumOfKPairs(array1, array2, k));

        scanner.close();
    }

    public static int findMinSumOfKPairs(int[] array1, int[] array2, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        // 初始化最小堆，将array1的第一个元素与array2的所有元素配对并插入堆中
        for (int j = 0; j < array2.length && j < k; j++) {
            minHeap.offer(new int[]{array1[0] + array2[j], 0, j});
        }

        int sum = 0;
        while (k > 0) {
            int[] pair = minHeap.poll();
            assert pair != null;
            sum += pair[0];
            int i = pair[1];
            int j = pair[2];

            // 如果array1还有剩余元素，则将下一个元素与array2的当前元素配对并插入堆中
            if (i + 1 < array1.length) {
                minHeap.offer(new int[]{array1[i + 1] + array2[j], i + 1, j});
            }

            k--;
        }

        return sum;
    }
}

运行步骤解析：

3 1 1 2
3 1 2 3
2

我们可以按照以下步骤解析并运行算法来求解整数对的最小和。

输入解析

1. 第一行表示数组array1的大小为3，元素为1, 1, 2。
2. 第二行表示数组array2的大小为3，元素为1, 2, 3。
3. 第三行表示需要取出的元素对数量k为2。

算法步骤

我们将使用最小堆优化的方法来求解这个问题。

1. 初始化最小堆：

   • 将array1的第一个元素1与array2的所有元素（1, 2, 3）配对，并将这些配对的和（2, 3, 4）以及对应的array1和array2的下标（0, 0）, (0, 1), (0, 2)插入最小堆中。
   • 最小堆中的元素现在为：[(2, 0, 0), (3, 0, 1), (4, 0, 2)]（注意：这里只展示了和与下标，实际在Java代码中会使用一个数组或对象来表示这些信息）。

2. 从最小堆中取出元素对：

   • 取出和最小的元素对(2, 0, 0)，将其和2加入结果sum中，此时sum=2。
   • 更新最小堆：由于我们已经使用了array1的第0个元素和array2的第0个元素，我们需要将array1的第1个元素（也是1，因为array1中有重复元素）与array2的第0个元素配对，并插入堆中。即插入(2, 1, 0)。
   • 最小堆更新后为：[(3, 0, 1), (4, 0, 2), (2, 1, 0)]。

3. 继续取出元素对：

   • 再次取出和最小的元素对(2, 1, 0)，将其和2加入结果sum中，此时sum=4。
   • 由于k已经为1（原本为2，已经取出了一对），我们只需要再取一对即可。但在这个例子中，为了完整性，我们假设k仍然大于0并继续操作（在实际代码中会有k的递减和检查）。
   • 由于我们已经使用了array1的前两个元素和array2的第0个元素，理论上我们应该继续将array1的下一个未使用元素与array2的当前或下一个未使用元素配对。但在这个例子中，由于k已经足够，我们可以停止。

然而，在这个特定的例子中，由于array1有重复元素，并且我们只需要取两对，所以实际上我们不需要继续扩展堆。但为了说明算法的一般性，我们展示了如何继续操作。

4. 如果k仍然大于0，我们会继续从堆中取出元素对，并更新堆，直到k为0。

结果

对于给定的输入，我们只需要取出两对元素对即可，它们分别是(1, 1)和(1, 1)，其和为2+2=4。但需要注意的是，由于array1中有重复元素，实际上我们取出的可能是(1来自array1的第0个位置, 1来自array2的第0个位置)和(1来自array1的第1个位置, 1来自array2的第0个位置)。在算法实现中，我们不需要关心具体是哪个位置的元素，只需要保证和最小即可。

注意事项

• 在实际实现中，我们需要确保不会重复使用相同的元素对（即相同的下标组合）。但由于数组是有序的，并且我们使用最小堆来维护元素对和，所以每次从堆中取出的都是当前可选元素对中和最小的那一对。
• 由于array1中有重复元素，所以可能存在多个元素对具有相同的和。在这种情况下，算法仍然有效，因为它会始终选择当前可选元素对中和最小的那一对（即使有多对具有相同的和）。

最终，对于给定的输入，算法将输出4作为整数对的最小和。