数据结构
网络
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 次浏览
广告