java - 从 NavigableSet 中获取特定索引处的元素

Question

我有一个NavigableSet，我想得到它的中间对象。

因为它是 a NavigableSet，所以我知道它是排序的，因此我知道它的中位数要么是中间元素，要么是两个中间元素的算术中间。

因此，我想访问 处的元素set.size() / 2，但NavigableSet界面不允许我访问。

有没有一种简单的方法来获取特定元素而无需手动遍历集合？

Answer 1

Strings are ordered alphabetically, have a look at this small example:

Edit: Now it really does what you wanted.

public static void main(String[] args) {
    NavigableSet<String> set = new TreeSet<String>();
    set.add("gamma");
    set.add("alpha");
    set.add("beta");

    System.out.println(Arrays.toString(set.toArray()));

    int indexOfGamma = set.headSet("gamma").size();

    System.out.println(indexOfGamma);

    System.out.println(get(set, set.first(), indexOfGamma));
}

public static String get(NavigableSet<String> set, String e, int index) {
    if (index == 0) {
        return e;
    }
    return get(set, set.higher(e), --index);
}

This is the output:

[alpha, beta, gamma]
2
gamma

I didn't do any benchmarks with greater data-sets, but I guess it should perform quite decent. The higher() method should directly point to the next element in the tree.

Answer 2

Yes set 不允许您从特定索引中获取元素。但我认为，如果您将其转换为数组，那么您将能够实现您所需要的。我试过这个示例代码，看看它是否有帮助：

NavigableSet set = new TreeSet<Integer>();
set.add(new Integer(5));
set.add(new Integer(4));
set.add(new Integer(3));
set.add(new Integer(2));
set.add(new Integer(1));
Integer medianIndex = set.size()/2;
System.out.println(set.toArray()[medianIndex]);

输出：3

Answer 3

除了迭代设置的“索引”次数之外，我找不到任何方法。然而，由于我们知道集合的大小，我们可以通过使用升序和降序迭代将其加速到至少一半的大小：

public static <T> T getInNavigableSetByIndex(NavigableSet<T> set, int index) {
    Objects.requireNonNull(set);

    final int size = set.size();

    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    final boolean descend = index >= size / 2;
    final Iterator<T> itr = descend ? set.descendingIterator() : set.iterator();
    final int stepCount = descend ? size - index : index + 1;
    T object = null;

    for (int i = 0; i < stepCount && itr.hasNext(); i++) {
        object = itr.next();
    }

    return object;
}