TypeScript中高效比较一维数组公共值及计算相似度的最优方案

针对你提出的需求，以下分字符串数组和自定义对象数组两种场景给出高效实现方案：

一、字符串数组场景 #

1. 判断是否存在公共值 #

利用Set的O(1)查询特性，把其中一个数组转成Set后，遍历另一个数组检查元素是否存在，整体时间复杂度为O(n+m)，远优于嵌套循环的O(n*m)。

function hasCommonValue(strArr1: string[], strArr2: string[]): boolean {
    const valueSet = new Set(strArr1);
    return strArr2.some(item => valueSet.has(item));
}

// 测试用例
console.log(hasCommonValue(["a", "b", "c"], ["c", "d"])); // 输出: true
console.log(hasCommonValue(["a", "b"], ["c", "d"])); // 输出: false

2. 计算数组相似度 #

按照你给出的规则：

• 数组长度相同且全匹配时相似度100%
• 匹配元素数除以两个数组的最大长度再乘以100%（对应示例中["a","b"]与["a"]相似度50%的情况）

实现代码：

function calculateStringSimilarity(strArr1: string[], strArr2: string[]): number {
    const valueSet = new Set(strArr1);
    const matchCount = strArr2.filter(item => valueSet.has(item)).length;
    const maxLength = Math.max(strArr1.length, strArr2.length);
    
    return maxLength === 0 ? 0 : (matchCount / maxLength) * 100;
}

// 测试用例
console.log(calculateStringSimilarity(["a", "b"], ["a", "b"])); // 输出: 100
console.log(calculateStringSimilarity(["a", "b"], ["a"])); // 输出: 50
console.log(calculateStringSimilarity(["a", "b", "c"], ["b", "d"])); // 输出: ~33.33

如果你的相似度规则是基于总元素数（即匹配数×2/(数组1长度+数组2长度)×100%），只需把分母改成strArr1.length + strArr2.length即可。

二、自定义对象数组场景 #

当元素是自带compare方法的自定义对象时，无法依赖Set的默认相等判断，需要基于compare方法实现逻辑。

1. 先定义对象类型 #

声明带有compare方法的接口，并实现示例对象：

interface Comparable {
    compare(other: this): boolean;
}

// 示例自定义对象：User类
class User implements Comparable {
    constructor(public id: number, public name: string) {}

    // 自定义相等判断逻辑
    compare(other: User): boolean {
        return this.id === other.id && this.name === other.name;
    }
}

2. 判断是否存在公共值 #

优先遍历较短数组，减少循环次数，对每个元素用compare方法在另一个数组中查找匹配：

function hasCommonObject<T extends Comparable>(arr1: T[], arr2: T[]): boolean {
    const [shortArr, longArr] = arr1.length <= arr2.length ? [arr1, arr2] : [arr2, arr1];
    return shortArr.some(item => longArr.some(other => item.compare(other)));
}

// 测试用例
const user1 = new User(1, "Alice");
const user2 = new User(2, "Bob");
const user3 = new User(1, "Alice");
console.log(hasCommonObject([user1, user2], [user3, new User(3, "Charlie")])); // 输出: true

3. 计算对象数组相似度 #

基于匹配元素数和最大长度的比值计算，同时标记已匹配元素避免重复计数（因为数组元素唯一）：

function calculateObjectSimilarity<T extends Comparable>(arr1: T[], arr2: T[]): number {
    const [shortArr, longArr] = arr1.length <= arr2.length ? [arr1, arr2] : [arr2, arr1];
    let matchCount = 0;
    const matchedIndices = new Set<number>(); // 标记已匹配的长数组元素索引

    for (const item of shortArr) {
        for (let i = 0; i < longArr.length; i++) {
            if (!matchedIndices.has(i) && item.compare(longArr[i])) {
                matchCount++;
                matchedIndices.add(i);
                break;
            }
        }
    }

    const maxLength = Math.max(arr1.length, arr2.length);
    return maxLength === 0 ? 0 : (matchCount / maxLength) * 100;
}

// 测试用例
console.log(calculateObjectSimilarity([user1, user2], [user3, user2])); // 输出: 100
console.log(calculateObjectSimilarity([user1, user2], [user3])); // 输出: 50

性能优化（针对大数据量） #

如果对象的compare方法依赖某个唯一标识（比如User的id），可以先建立标识到对象的映射表，把时间复杂度降到O(n+m)：

function hasCommonObjectOptimized<T extends Comparable & { id: number }>(arr1: T[], arr2: T[]): boolean {
    const idMap = new Map<number, T>();
    arr1.forEach(item => idMap.set(item.id, item));

    return arr2.some(item => {
        const target = idMap.get(item.id);
        return target ? item.compare(target) : false;
    });
}

注意：这种优化需要你能确定对象的唯一标识字段，否则只能用双层循环的方式。

内容的提问来源于stack exchange，提问作者Sreehari S