| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 2 | maomao90 | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Is there any way to get index of an element in TreeSet?
I want a data structure(like set in c++) which can handle deletions in O(1) and do search(like lower_bound in c++) in O(logn) time.
Is there any inbuilt data structure in Java which supports the above operations?
Lol. How do you even maintain an ordering of elements with O(1) deletion time? Unless you tell me that you are only deleting the largest/smallest element at any one time.
C++ has std:set which is a sorted container and performs erase(int position) in O(1). I just asked if there is a equivalent data structure of Set in Java which supports those operations. What's there to laugh in that ?
std::set erases by iterator in o(1), KeyIterator.remove also works in amortized constant.
I do not know of standard library navigable set with quick access by index
In C++, we have lower_bound for set which returns the "index" of required element in O(logn).In Java, we have TreeSet.ceiling method which does almost the same thing except for the fact that it returns the "element" itself and not the index. To find the index of that element, it will take O(n) time.
Do you know any way to achieve this in java ?
Unfortunately calling size() on subSet would work on O(size), so no, there is none in standard library
Thanks for replying. So how do we solve problems which require such operations within the required time limit ?
I do have alternative set in my library, namely TreapSet, and with CHelper I can use it seamlessly.
Its iterator is not optimized though
Is this the one you are saying ?https://ideone.com/BBqInQ
That is most of it, though https://github.com/EgorKulikov/yaal/blob/master/lib/main/net/egork/collections/set/TreapSet.java is up to date
Ok, thanks a lot.