JavaScript：如何线性验证数组元素是否≥另一数组元素的两倍

嘿，你的这个问题其实不用嵌套循环就能高效解决！先说说原来嵌套循环的问题：它的时间复杂度是O(n*m)，当两个数组的长度很大时，性能会急剧下降。我们可以通过拆解问题本质，把复杂度降到**O(n + m)**的线性级别。

问题本质拆解 #

我们需要判断：arr2中是否存在任意元素x，使得x >= 2*y（y是arr1中的任意元素）。

换个角度想：

• 要让x >= 2*y成立，最容易满足的情况是：用arr2里最大的元素去对比arr1里最小的元素的两倍。
  • 如果arr2的最大值都能 >= 2*arr1的最小值，那这个最大值肯定能满足和arr1里最小元素的倍数关系，直接返回true。
  • 如果连arr2的最大值都 < 2arr1的最小值，那arr2里所有元素都会小于arr1中每个元素的两倍（因为arr1里的元素都≥最小值，2元素≥2*最小值>arr2所有元素），这时候返回false。

实现代码（JavaScript） #

function hasValidElement(arr1, arr2) {
    // 处理空数组的边界情况：没有元素可比较时返回false
    if (arr1.length === 0 || arr2.length === 0) {
        return false;
    }
    
    // 线性遍历找到arr1的最小值和arr2的最大值
    const minArr1 = Math.min(...arr1);
    const maxArr2 = Math.max(...arr2);
    
    // 核心判断逻辑
    return maxArr2 >= 2 * minArr1;
}

// 测试你的示例
let arr1 = [1,2,3,4,5];
let arr2 = [6,7,8,9,10];
console.log(hasValidElement(arr1, arr2)); // 输出 true

// 测试反例：arr2元素都不满足条件
let arr3 = [3,4,5];
let arr4 = [5];
console.log(hasValidElement(arr3, arr4)); // 输出 false

复杂度分析 #

• Math.min(...arr1) 和 Math.max(...arr2) 各自都是线性遍历数组，时间复杂度分别为O(n)和O(m)（n是arr1长度，m是arr2长度）。
• 整体时间复杂度为O(n + m)，完全符合线性时间的要求。

内容的提问来源于stack exchange，提问作者Olamilekan Ibrahim