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]

解释 − 前4对是从序列 [2, 1], [2, 3], [4, 1], [4, 3], [6, 1], [6, 3], [8, 1], [6, 5], [8, 3], [8, 5], [6, 7], [8, 7] 返回的

现在让我们来看看解决上述问题的各种方法。

方法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个最小和的配对存储起来。我们只需在每一步中将对应较小元素的指针向前移动来使这个过程尽可能高效。

我们可以从这个双指针方法中观察到上述问题的时间复杂度为O(klogk)，这比暴力方法所需的O(n^2)时间复杂度要快得多。

算法

将指针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>