3 ms·
Look at jallmanns comment [0]. Quickselect partially sorts the input array. If you reuse that array it will be faster on repeated runs. [0] https://news.ycombi
by qznc 13y ago
Look at jallmanns comment [0]. Quickselect partially sorts the input array. If you reuse that array it will be faster on repeated runs.
[0] https://news.ycombinator.com/item?id=5728220 https://news.ycombinator.com/item?id=5728220
- andrewcooke 13y agoeven w ordered data, sorting is O(n) isn't it?
- sp332 13y agoOrdered data? Lookups into sorted data can use a binary search and are only O(log n).
- andrewcooke 13y agobut you need to move n/2 to "make room" - think of the whole process. edit: you're not wrong, but what i am saying is that to make the filter practical you have to save the new point, too. sorry for brief comments. on vacn w tablet only.
- deleted 13y ago[deleted]