在一个数组中查找小于或等于另一个数组中的数字的数字?

Question

如果给定arr1[1， 2， 3]和arr2[2， 4]，我需要找到arr1中有多少元素小于或等于arr2中的每个元素。对于这些数组，输出应该是 [2， 3]，因为 arr1 中的 2 个元素小于或等于 arr2[1]，arr1 中的 3 个元素小于或等于 arr2[2]。

我已经以一种天真的方式解决了这个问题，但我想降低运行时的复杂性 - 这个解决方案根本不能很好地处理大型数组。谁能阐明我如何重构它以降低复杂性？

counts([1, 2, 3] ,[2, 4])
function counts(nums, maxes) {
let newArr = [];
for(let i = 0; i < maxes.length; i++){
let count = 0;
for(let j = 0; j < nums.length; j++){
if(nums[j] <= maxes[i]){
count++;
}
}
newArr.push(count);
}
console.log(newArr);
}

Answer 1

我将从对第一个数组进行排序开始。然后，对于第二个数组中的每个元素，使用二叉搜索查找它将插入到第一个数组中的位置(但实际上不要插入它(。此索引将告诉您第一个数组中有多少元素小于或等于第二个数组中的该元素。将其附加到结果数组并继续。这具有 O(n log n( 的复杂性，n 是较大数组的大小。

counts([1, 2, 3] ,[2, 4])
function counts(nums, maxes) {
nums.sort();
let result = [];
for(let i = 0; i < maxes.length; i++){
let index = binarySearch(maxes[i], nums);
result.push(index);
}
console.log(result);
}

我在这里没有包含binarySearch的代码，但它会在 O(log n( 时间内找到大于maxes[i]nums最小项目的索引。请参阅维基百科关于二进制搜索的文章。

Answer 2

var res =  arr2.map(x => arr1.filter(elem => elem<=x).length);

Answer 3

看看二进制搜索，基本上你每一步都减少了你的收藏。二叉搜索

Answer 4

你可以试试这个方法

const comapreArrays = (arr1,arr2) => {
return arr1.map(numInFirstArray => arr2.filter(numInSecArray => 
numInFirstArray <= numInSecArray).length);
}

Answer 5

var arr1=[1,5,3];
var arr2=[2,4];
var res = arr2.map(element=>{
var count=0;
arr1.forEach(function(i){
if(i<=element)
count++;
});
return count;
});
alert(res);

Answer 6

这是一种不同的方法，首先对两个数组(或副本(进行排序，然后在索引变量上闭包，并将最后找到的索引(加一(映射到相应的搜索值。

结果实际上是一个用于Map的计数排序数组。然后返回映射的索引。

function fn(a, b) {
const
ASC = (a, b) => a - b;
var indices;
a.sort(ASC);
indices = new Map(
b.slice().sort(ASC).map((i => v => {
while (i in a && a[i] <= v) ++i;
return [v, i];
})(0))
);
return b.map(v => indices.get(v));
}
console.log(fn([1, 2, 3], [2, 4]));