这不是一个好方法,IMO.如果您使用的Collections.sort(list)地方list是a LinkedList,则将list其复制到临时数组,对其进行排序,然后将其复制回列表,即O(NlogN)排序加上2 * O(N)副本.但是当你尝试进行二进制搜索时(例如使用Collections.binarySearch(list),每个搜索都会进行O(N)列表遍历操作.所以你可能也没有打扰排序列表!
另一种方法是将列表转换为数组或ArrayList,然后对该数组/ ArrayList进行排序和搜索.这给了一个副本加一种设置和O(logN)每次搜索.
但这些都不是最好的方法.这取决于您需要执行搜索操作的次数.
如果你只是想在列表上进行一次搜索,那么调用list.contains(...)是O(N)......这比涉及排序和二进制搜索的任何事情要好.
如果要对永不更改的列表执行多次搜索,最好将列表条目放入HashSet中.构造HashSet是O(N)和搜索是O(1).(这假设您不需要自己的比较器.)
如果要对不断更改订单不重要的列表执行多次搜索,请将列表替换为HashSet.更新HashSet的增量成本将O(1)用于每次添加/删除以及O(1)每次搜索.
如果要对不断更改且订单重要的列表执行多次搜索,请将列表替换为插入顺序的LinkedHashMap.这将是O(1)每次添加/删除,以及O(1)每次搜索...但具有大比例常数而不是HashSet.
| 归档时间： |
|
| 查看次数： |
200 次 |
| 最近记录： |