当前位置: 面试刷题>> 映射配对之和 (经典算法题500道)


### 题目描述补充 **题目:映射配对之和** 给定两个整数数组 `nums1` 和 `nums2`,其中 `nums1` 中的每个元素都唯一对应 `nums2` 中的一个元素(通过某种未知的映射关系),但对应关系未直接给出。你的任务是找到一种映射方式,使得 `nums1` 中每个元素与其在 `nums2` 中对应元素的配对之和的总和最小。 **注意**: 1. `nums1` 和 `nums2` 的长度相同,且都不为空。 2. `nums1` 和 `nums2` 中的元素都是非负整数。 ### 示例 **输入**: ``` nums1 = [1, 2, 3] nums2 = [4, 5, 6] ``` **输出**: 由于映射关系未知,我们需要尝试所有可能的映射,并计算每种映射下的配对之和的总和。在这个例子中,最小总和为 `1*4 + 2*5 + 3*6 = 32`(但注意,实际实现中我们不需要列出所有可能,而是通过排序和贪心算法找到最小和)。 ### 解题思路 为了找到最小的配对之和,我们可以对两个数组进行排序,然后逐一配对排序后的数组中的元素(即 `nums1` 的第 `i` 小元素与 `nums2` 的第 `i` 小元素配对),这样可以保证每一对元素的和尽可能小。 ### PHP 代码示例 ```php function minSumPair($nums1, $nums2) { sort($nums1); sort($nums2); $n = count($nums1); $sum = 0; for ($i = 0; $i < $n; $i++) { $sum += $nums1[$i] * $nums2[$i]; } return $sum; } // 示例用法 $nums1 = [1, 2, 3]; $nums2 = [4, 5, 6]; echo minSumPair($nums1, $nums2); // 输出 32 ``` ### Python 代码示例 ```python def min_sum_pair(nums1, nums2): nums1.sort() nums2.sort() return sum(a*b for a, b in zip(nums1, nums2)) # 示例用法 nums1 = [1, 2, 3] nums2 = [4, 5, 6] print(min_sum_pair(nums1, nums2)) # 输出 32 ``` ### JavaScript 代码示例 ```javascript function minSumPair(nums1, nums2) { nums1.sort((a, b) => a - b); nums2.sort((a, b) => a - b); let sum = 0; for (let i = 0; i < nums1.length; i++) { sum += nums1[i] * nums2[i]; } return sum; } // 示例用法 let nums1 = [1, 2, 3]; let nums2 = [4, 5, 6]; console.log(minSumPair(nums1, nums2)); // 输出 32 ``` **码小课网站中有更多相关内容分享给大家学习**,可以访问码小课获取更多算法和数据结构的知识。
推荐面试题