匹配算法：向下就近原则，向下没有就向上

匹配算法：向下就近原则，向下没有就向上 实现方式一实现方式二总结

实现方式一 private static List<Integer> findMatches(List<Integer> sourceList, List<Integer> searchValues) { List<Integer> sortedList = sourceList.stream().filter(Objects::nonNull).sorted() .collect(Collectors.toList()); Set<Integer> foundValues = new HashSet<>(); for (Integer searchValue : searchValues) { Integer nearestValue = findNearestBelowOrAbove(sortedList, searchValue); if (nearestValue != null) { foundValues.add(nearestValue); } } return sourceList.stream().filter(foundValues::contains) .collect(Collectors.toList()); } /** * @param sortedList * @param searchValue * @return 匹配结果（匹配规则：向下就近原则，向下没有就向上） */ private static Integer findNearestBelowOrAbove(List<Integer> sortedList, Integer searchValue) { if (sortedList.isEmpty()) { return null; } int index = Collections.binarySearch(sortedList, searchValue); if (index >= 0) { return sortedList.get(index); } else { int insertionPoint = -(index + 1); if (insertionPoint < sortedList.size()) { return sortedList.get(insertionPoint); } else { return sortedList.get(sortedList.size() - 1); } } } 实现方式二 public static List<Integer> findMatches(List<Integer> sourceList, List<Integer> searchValues) { // 过滤 null 值并排序 TreeSet<Integer> sortedSet = sourceList.stream() .filter(Objects::nonNull) .collect(Collectors.toCollection(TreeSet::new)); Set<Integer> foundValues = new HashSet<>(); for (Integer searchValue : searchValues) { Integer nearestValue = findNearestBelowOrAbove(sortedSet, searchValue); if (nearestValue != null) { foundValues.add(nearestValue); } } // 保持原始顺序 return sourceList.stream() .filter(foundValues::contains) .collect(Collectors.toList()); } private static Integer findNearestBelowOrAbove(TreeSet<Integer> sortedSet, Integer searchValue) { // 查找大于等于 searchValue 的最小值 Integer ceiling = sortedSet.ceiling(searchValue); if (ceiling != null) { return ceiling; } // 查找小于等于 searchValue 的最大值 Integer floor = sortedSet.floor(searchValue); if (floor != null) { return floor; } return null; }

测试代码：

public class TestMatcher { public static void main(String[] args) { List<Integer> sourceList = Arrays.asList(5, 7, 11, 31, 77); List<Integer> searchValues = Arrays.asList(1, 2, 8, 12, 13, 14, 15, 82, 91); List<Integer> matches = findMatches(sourceList, searchValues); System.out.println(matches); } }

测试结果： [5, 11, 31, 77]

总结

两种实现的时间复杂度相同，都是 O(n log n)。 如果数据是静态的，使用 基于排序列表的实现。 如果数据需要频繁更新，使用 基于 TreeSet 的实现。