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 _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/SQINWYIB4FXXZM5V3LGMVEB6JBGIXHRT/ Code of Conduct: http://python.org/psf/codeofconduct/
