数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript 程序：查找两个数组中和最小的 k 对
在本文中，我们将首先找到两个数组可以组成的所有对。然后，根据 k 的值，我们将显示两个数组中和最小的对。
在这里，我们将首先使用暴力方法来解决问题，然后我们将使用各种方法对其进行优化。因此，让我们从问题陈述和一些示例开始。
问题陈述
我们得到了两个数组 arr1[] 和 arr2[]，它们按升序排序，以及一个非负整数 k，目标是找到 k 对和最小的对，使得每对的一个元素属于 arr1[]，另一个元素属于 arr2[]。让我们看一些例子来澄清我们的概念。
示例
输入
arr1[] = [2, 3, 6, 7, 9] arr2[] = [1, 4, 8, 10] k = 1
输出
[2, 1]
解释 − 和最小的第一对是 [2, 1]，它来自 [2, 1]、[3, 1]、[6, 1]、[7, 1]、[9, 1]、[2, 4]、[3, 4]、[6, 4]、[7, 4]、[9, 4]、[2, 8]、[3, 8]、[6, 8]、[7, 8]、[9, 8]、[2, 10]、[3, 10]、[6, 10]、[7, 10]、[9, 10]。
示例
输入
arr1[] = {2, 4, 6, 8}
arr2[] = {1, 3, 5, 7}
k = 4
输出
[2, 1], [2, 3], [4, 1], [4, 3]
解释 − 从序列 [2, 1]、[2, 3]、[4, 1]、[4, 3]、[6, 1]、[6, 3]、[8, 1]、[6, 5]、[8, 3]、[8, 5]、[6, 7]、[8, 7] 中返回前 4 对。
现在让我们看看解决上述问题的各种方法。
方法 1：暴力法
解决此问题的暴力方法包括从给定的两个数组生成所有可能的对，然后选择和最小的 k 对。这种方法的时间复杂度为 O(n^2 log n)，对于大型输入而言效率不高。
算法
初始化一个名为“pairs”的空列表以存储所有可能的对。
遍历第一个数组“arr1”中的每个元素“a”。
遍历第二个数组“arr2”中的每个元素“b”。
将新的对“[a, b]”及其和“a + b”添加到“pairs”列表中。
根据每对的和，按升序对“pairs”列表进行排序。
从排序的“pairs”列表中提取前“k”对。
返回“k”对作为结果。
示例
<!DOCTYPE html>
<html>
<body>
<div>
<h3>Given Arrays:</h3>
<p id="arr1"></p>
<p id="arr2"></p>
</div>
<div>
<label for="k">Enter k:</label>
<input type="number" id="k" name="k" value="2">
<button onclick="findKPairs()">Find</button>
</div>
<div id="output"></div>
<script>
let arr1 = [1, 7, 11];
let arr2 = [2, 4, 6];
const kInput = document.getElementById('k');
const output = document.getElementById('output');
const arr1El = document.getElementById('arr1');
const arr2El = document.getElementById('arr2');
function displayArrays() {
arr1El.textContent = `arr1 = [${arr1.join(', ')}]`;
arr2El.textContent = `arr2 = [${arr2.join(', ')}]`;
}
function findKPairs() {
const k = parseInt(kInput.value);
let pairs = [];
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2.length; j++) {
pairs.push([arr1[i], arr2[j], arr1[i] + arr2[j]]);
}
}
pairs.sort((a, b) => a[2] - b[2]);
const result = pairs.slice(0, k).map(pair => `[${pair[0]}, ${pair[1]}]`);
output.innerHTML = result;
}
displayArrays();
</script>
</body>
</html>
方法 2：双指针法
双指针法需要为每个数组初始化两个指针，分别指向数组的开头。最后，使用这些指针，我们遍历数组，比较当前指针位置元素的和，并存储具有 k 个最小和的对。为了使此过程尽可能高效，我们只需在每个步骤中将对应于较小元素的指针向前移动 1。
我们可以从这种双指针方法中观察到，上述问题的时间复杂度为 O(k log k)，这比暴力方法所需的 O(n2) 时间复杂度快得多。
算法
将指针 i 和 j 分别初始化为数组 nums1 和 nums2 的开头。
初始化一个空列表 pair 以存储和最小的 k 对。
当两个指针 i 和 j 都在各自数组的边界内，并且 pairs 的长度小于 k 时 −
计算当前指针位置元素的和，并将此对添加到 pairs 中。
如果 nums1[i] 小于或等于 nums2[j]，则将指针 i 向前移动 1。否则，将指针 j 向前移动 1。
返回 pairs。
示例
<!DOCTYPE html>
<html>
<body>
<div id="input"></div>
<div id="output"></div>
<script>
function findKPairsWithSmallestSums(nums1, nums2, k) {
const pairs = [];
let i = 0,
j = 0;
while (i < nums1.length && j < nums2.length && pairs.length < k) {
const sum = nums1[i] + nums2[j];
pairs.push([nums1[i], nums2[j], sum]);
if (nums1[i] <= nums2[j]) {
i++;
} else {
j++;
}
}
return pairs;
}
// Example usage
const nums1 = [1, 2, 4, 5, 6];
const nums2 = [1, 3, 4, 7, 8];
const k = 3;
// Display the input arrays using innerHTML
const inputDiv = document.getElementById("input");
inputDiv.innerHTML = `<h3>Input arrays:</h3>nums1 = [${nums1}], nums2 = [${nums2}]<br><br>`;
const pairs = findKPairsWithSmallestSums(nums1, nums2, k);
// Display the results using innerHTML
const outputDiv = document.getElementById("output");
outputDiv.innerHTML = "<h3>K pairs with smallest sums:</h3>";
for (let i = 0; i < pairs.length; i++) {
outputDiv.innerHTML += `[${pairs[i][0]}, ${pairs[i][1]}] = ${pairs[i][2]}<br>`;
}
</script>
</body>
</html>
结论
在本教程中，我们讨论了编写一个程序来查找两个数组中和最小的 k 对。我们首先使用暴力方法，然后使用双指针方法对其进行了优化。
213 次浏览
