java - 查找最相似的 List<String> 的有效方法

Question

我有一个list1<String>等1000 list<String> 。我需要选择具有最精确匹配值的列表。

今天我回顾一下每个 list<String>与 list1 进行比较，将覆盖范围保存在某个排序列表中，最后选择最相似的列表。

public static <T> List<T> intersection(List<T> list1, List<T> list2) {
        List<T> list = new ArrayList<T>();

        for (T t : list1) {
            if(list2.contains(t)) {
                list.add(t);
            }
        }

        return list;
    }

假设我也有很多列表需要比较，那么遍历所有 1000 个唯一列表的操作会浪费时间。

您能否建议我一种有效的方法/算法来做到这一点？

Answer 1

您的列表未排序，因此任何 contains() 操作都需要搜索整个列表(或者直到找到为止，平均为 N/2)。
因此，首先对所有列表进行排序 (Collections.sort())，然后使用 Collections.binarySearch() 查找是否包含该 String。这只需要 (log N) 而不是以前的 N/2。