Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - Take every k-th element from the (1 .. n) natural numbers series

For example, we have series 1, 2, 3, 4, 5. We take every 3 element => 3, 1, 5, 2, 4 (chosen element shouldn't remain, we can take while series is not empty). Naive implementation by circle doubly linked list is not good idea cause of performance. Can you give me an advice which data structures and algorithms are more applicable?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

If you just need the last number, it's known as Josephus problem and there're well-known formulas for computing the answer in O(N) time.

I don't know if one can adapt it to run a full simulation, so I'll describe a straightforward O(N log N) solution here:

Let's keep all numbers in a treap with implicit keys. We need to find the k-th element and delete it at each step (in fact, there can be a shift, so it's more like (cur_shift + k) % cur_size, but it doesn't really matter). A treap can do it. We just need to split it into 3 parts [0, k - 1], [k, k] and [k + 1, cur_size - 1], print the number in the node that corresponds to the second part and merge the first and last part back together. It requires O(log N) time per step, so it should be good enough for the given constraints.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...