Algorithm, Part I — Successor with delete – Steel Wings
Q: Successor with delete. Given a set of N integers S={0,1,…,N−1} and a sequence of requests of the following form:
- Remove x from S
- Find the successor of x: the smallest y in S such that y≥x.
design a data type so that all operations (except construction) should take logarithmic time or better.
(Java Code on github at the bottom of the post. )
My thoughts and solutions:
Well, I have experienced some frustration on this one. Since it is under the context of Union-Find, it is very likely that we need to use Union-Find algorithm. Unfortunately, I didn't figure out how to apply Union-Find. One step back, if there was no context at all, I probably would not think of using Union-Find at all…But we know now…Again, this suggests that we should practice more problems as the knowledge base, otherwise we won't have any previous experience to connect with when facing a new problem.
Read full article from Algorithm, Part I — Successor with delete – Steel Wings
No comments:
Post a Comment