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. -- Steve