如何在树集中查找元素的索引？

algorithm data-structures java treeset sortedset

2022-09-01 09:15:38

我正在使用a，我只想在集合中找到一个数字的索引。有没有一个很好的方法来做到这一点，实际上利用了二叉树的O（log（n））复杂性？TreeSet<Integer>

（如果没有，我该怎么办，有谁知道为什么不呢？我很好奇为什么这样的类会包含在Java中而没有像搜索函数这样的东西。

答案 1

我仔细研究了TreeSet及其接口一段时间，我发现获取元素索引的最佳方法是：

set.headSet(element).size()

headSet(element)返回小于其参数的元素的子，因此此集合的大小将是所讨论元素的索引。这确实是一个奇怪的解决方案。TreeSet

答案 2

正如@Yrlec指出的那样，will返回0，尽管集合中没有这个元素。所以我们最好检查：set.headSet(element).size

 return set.contains(element)? set.headSet(element).size(): -1;

下面是一个测试用例来显示问题：

public static void main(String args[]){
    TreeSet<Integer> set = new TreeSet<>();
    set.add(4);
    set.add(2);
    set.add(3);
    set.add(1);

    System.out.println(set.headSet(1).size());//0
    System.out.println(set.headSet(2).size());//1
    System.out.println(set.headSet(3).size());//2
    System.out.println(set.headSet(4).size());//3
    System.out.println(set.headSet(-1).size());//0!!Caution,returns 0 though it does not exist!

}