如何从 Java TreeMap 中的给定键迭代
How to iterate from a given key in Java TreeMap
我有一个 TreeMap，想得到一组大于给定值的 K 个最小键（条目）。
我知道我们可以使用 higherKey(givenValue) 获取唯一的密钥，但是我应该如何从那里迭代？
一种可能的方法是从大于给定值的最小键获取 tailMap，但如果 K 与地图大小相比较小，那就太过分了。
有没有更好的O(logn + K)时间复杂度的方法？
这里的错误是认为tailMap制作了一张新地图。它没有。它为您提供了一个轻量级对象，基本上只包含一个指向原始地图的字段和枢轴点，仅此而已。因此，您对 tailMap 地图所做的任何更改也会影响底层地图，而对底层地图所做的任何更改也会影响您的 tailMap。
for (KeyType key : treeMap.tailMap(pivot).keySet()) {
}
上面的是O(logn)操作的tailMap复杂度，给你循环，增加K到地段，总计 O(logn+K) 的时间复杂度和 O(1) space 的复杂度，其中 N 是地图的大小，K 是最终位于地图选定一侧的键的数量枢轴点（所以，最坏的情况，O(nlogn)）。
如果你想要一个实际复制的地图，你会这样做：
TreeMap<KeyType> tm = new TreeMap<KeyType>(original.tailMap(pivot));
请注意，如果您指定了自定义比较器，这也会复制使用过的比较器。这确实是 O(logn + K) 的时间复杂度（和 O(K) 的 space 复杂度）。当然，如果你循环遍历这段代码，它仍然是O(logn + K)（因为在谈论大 O 表示法时 2K 只是归结为 K）。
我有一个 TreeMap，想得到一组大于给定值的 K 个最小键（条目）。
我知道我们可以使用 higherKey(givenValue) 获取唯一的密钥，但是我应该如何从那里迭代？
一种可能的方法是从大于给定值的最小键获取 tailMap，但如果 K 与地图大小相比较小，那就太过分了。
有没有更好的O(logn + K)时间复杂度的方法？
这里的错误是认为tailMap制作了一张新地图。它没有。它为您提供了一个轻量级对象，基本上只包含一个指向原始地图的字段和枢轴点，仅此而已。因此，您对 tailMap 地图所做的任何更改也会影响底层地图，而对底层地图所做的任何更改也会影响您的 tailMap。
for (KeyType key : treeMap.tailMap(pivot).keySet()) {
}
上面的是O(logn)操作的tailMap复杂度，给你循环，增加K到地段，总计 O(logn+K) 的时间复杂度和 O(1) space 的复杂度，其中 N 是地图的大小，K 是最终位于地图选定一侧的键的数量枢轴点（所以，最坏的情况，O(nlogn)）。
如果你想要一个实际复制的地图，你会这样做：
TreeMap<KeyType> tm = new TreeMap<KeyType>(original.tailMap(pivot));
请注意，如果您指定了自定义比较器，这也会复制使用过的比较器。这确实是 O(logn + K) 的时间复杂度（和 O(K) 的 space 复杂度）。当然，如果你循环遍历这段代码，它仍然是O(logn + K)（因为在谈论大 O 表示法时 2K 只是归结为 K）。