資料結構
網路
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 次瀏覽
