当前位置: 面试刷题>> 映射配对之和 (经典算法题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
```
**码小课网站中有更多相关内容分享给大家学习**,可以访问码小课获取更多算法和数据结构的知识。