假设我有:
class Item {
int id;
int type;
}
我能做到:
List<Item> items;
Item itemToFind;
Comparator<Item> itemComparator;
Collections.binarySearch(items, itemToFind, itemComparator);
但是,假设我只得到对象的一个属性,而不是整个对象,比如说 type
对于上面的例子。假设列表按该属性排序,Java 中是否有标准方法或某些已建立的库来执行此操作:
List<Item> items;
Function<Item, Integer> typeExtractor = Item::getType;
int typeToFind;
Comparator<Integer> typeComparator = Integer::compare;
binarySearch(items, typeExtractor, typeToFind, typeComparator);
没有额外的开销(例如,将 List<Item>
转换为 List<Integer>
以调用 Collections.binarySearch
或类似的)?
最佳答案
你的问题是在 Collection<T>
java 的二进制搜索实现只允许搜索 T
类型的项目.为了搜索属于 T
的另一种类型,您可以执行以下操作:
- 将另一种类型包裹在
T
内,在你的情况下应该是这样的:
List<Item> items;
int typeToFind;
Item itemToFind = new Item(/* random value for id */ 0, typeToFind);
int index = binarySearch(items, itemToFind , (a, b) -> a.getType() - b.getType());
要在此处添加的一些重要说明:
-
- 项目的比较应该只依赖于“类型”,否则你可能会遇到一些讨厌的错误;
-
- 项目列表应该排序。排序应该只依赖于`type`(基本上使用与以前相同的比较器)
- 从初始列表创建一个新列表:
List<Items> items;
int typeToFind
int index = binarySearch(items.stream.map(item -> item.getType()).collect(Collectors.toList()), itemToFind);
据我所知,Java 的标准库不提供带有比较器的二进制搜索实现来实现键相等。如果这些选项不能满足您的要求,您可能应该搜索图书馆或实现您自己的搜索。
关于java - 带有 key 提取器的二进制搜索 Java 列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54244405/