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

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。