On 2021-12-25 23:52, Steven D'Aprano wrote:
On Thu, Dec 23, 2021 at 05:53:46PM -0000, Stefan Pochmann wrote:
Chris Angelico wrote:
If you're removing multiple, it's usually best to filter. This is a great opportunity to learn about list comprehensions and the difference between O(n) and O(n²) :) ChrisA
It would be O(n) if done right.
Can you sketch an O(n) algorithm for removing multiple items from an array, which *doesn't* involving building a temporary new list?
I thought of this:
- walk forward along the list, identifying the indices where the item equals the target;
- stop when you reach maxcount, or the end of the list;
- delete the indices in reverse order
which I am pretty sure minimises movement of the items, but that's still O(N**2). (To be precise, O(N*M) where M is the number of items to be removed.)
Anyway, it doesn't matter how efficient the code is if nobody uses it. Some use-cases would be nice.
It can be done with a pass to remove the matches and pack the list: Where there's a match, move it if you've exceeded maxcount, else skip it. Where there isn't a match, move it. followed by truncation of the list if necessary.