資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用於查詢兩個排序陣列中公共元素的 JavaScript 程式
我們需要編寫一個 JavaScript 函式，該函式接受兩個已排序的陣列（均按相同順序排序）。該函式應準備並返回一個第三個陣列，其中包含這兩個陣列共有的所有元素。
我們可以輕鬆地透過以 O(m * n) 時間解決此問題（m 和 n 是陣列的相應長度），甚至是 O(m + n)。
但是，由於陣列已排序，因此我們可以透過迭代較小的陣列並在大陣列中使用二分搜尋演算法搜尋元素來節省時間。
透過這種方式，函式的時間複雜度將降低到 O(n * logm)（m > n），這遠好於 O(m + n)，尤其是在 m >> n 的情況下
示例
程式碼如下−
const arr1 = [2, 5, 7, 8, 9, 11, 14];
const arr2 = [1, 3, 4, 5, 6, 8, 11, 16];
const binarySearch = (target, arr = []) => {
let first = 0;
let last = arr.length − 1;
let position = −1;
let found = false;
let middle;
while (found === false && first <= last) {
middle = Math.floor((first + last)/2);
if (arr[middle] == target) {
found = true;
position = middle;
} else if (arr[middle] > target) {
last = middle − 1;
} else {
first = middle + 1;
}
}
return position;
}
const findCommon = (arr1 = [], arr2 = []) => {
const res = [];
for (let i = 0; i < arr1.length; ++i){
if (binarySearch(arr1[i], arr2) !== −1){
res.push(arr1[i]);
};
};
return res;
};
console.log(findCommon(arr1, arr2));輸出
控制檯中的輸出將為−
[5, 8, 11]
更新於：24-Nov-2020
312 次瀏覽
廣告