python - Can I solve this in O(n)? - Stack Overflow

admin管理员组

文章数量:1297036

Here is a snippet of a problem below:

Given an array of integers, query, your service must perform as follows. Each integer is an item ID to be added to or removed from the cart.

If the query integer is positive, add the integer representing an item ID to the back of the cart.

If the integer is negative, remove the first occurrence of the integer from the cart.

Report an array that represents the final cart after processing all the queries. It is guaranteed that the final cart is non-empty and the integers in the queries are not equal to 0.

Example

Initially, there are n = 5 items in the cart:

cart = [1, 2, 1, 2, 1]
queries = [-1, -1, 3, 4, -3]

Steps

Query	Task	Cart State
-1	Delete first 1 from cart	[2, 1, 2, 1]
-1	Delete first 1 from cart	[2, 2, 1]
3	Append 3 to cart	[2, 2, 1, 3]
4	Append 4 to cart	[2, 2, 1, 3, 4]
-3	Delete first 3 from cart	[2, 2, 1, 4]

Here is a snippet of a problem below:

Given an array of integers, query, your service must perform as follows. Each integer is an item ID to be added to or removed from the cart.

If the query integer is positive, add the integer representing an item ID to the back of the cart.

If the integer is negative, remove the first occurrence of the integer from the cart.

Report an array that represents the final cart after processing all the queries. It is guaranteed that the final cart is non-empty and the integers in the queries are not equal to 0.

Example

Initially, there are n = 5 items in the cart:

cart = [1, 2, 1, 2, 1]
queries = [-1, -1, 3, 4, -3]

Steps

Query	Task	Cart State
-1	Delete first 1 from cart	[2, 1, 2, 1]
-1	Delete first 1 from cart	[2, 2, 1]
3	Append 3 to cart	[2, 2, 1, 3]
4	Append 4 to cart	[2, 2, 1, 3, 4]
-3	Delete first 3 from cart	[2, 2, 1, 4]

Final Output:

[2, 2, 1, 4]

I have no idea how to get this down from O(n^2) to O(n) Any ideas?

My code looked something like this:

def findFinalCart(cart, queries):
    for num in queries:
        if num > 0:
            cart.append(num)  # Append new elements
        else:
            value = abs(num)
            for i, x in enumerate(cart):
                if x == value:
                    del cart[i] 
                    break 
    return cart

• python

Share Improve this question Follow edited Feb 11 at 18:20 Barmar 783k5656 gold badges546546 silver badges660660 bronze badges asked Feb 11 at 17:45 Bringo JrBringo Jr 322 bronze badges 4

• 2 In addition, editing a list while iterating over it is asking for trouble. The indexing changes. – Mark Tolonen Commented Feb 11 at 18:02
• 1 Is the order of the final result important? If not, adding items to a collection.Counter() should be O(1). – JonSG Commented Feb 11 at 18:12
• @MarkTolonen What do you mean? As soon as the edit it, the stop the iteration. That is absolutely fine and normal. – no comment Commented Feb 11 at 19:00
• @nocomment Sorry, didn't notice the break. And use list.remove anyway instead of this loop. – Mark Tolonen Commented Feb 11 at 19:10

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 5

The initial contents of the cart can be treated exactly like queries. So first, combine the cart and queries into a single "pseudo-queries" list, and treat the cart as initially empty.

Go through the queries, and count how many times each ID will need to be removed. Then, go through and add items to the cart, but just don't add any items that will have to be removed.

import collections

queries = cart + queries
cart = []

removal_counts = collections.Counter(-x for x in queries if x < 0)
for item in queries:
    if item < 0:
        continue
    if removal_counts[item]:
        removal_counts[item] -= 1
    else:
        cart.append(item)

本文标签： pythonCan I solve this in O(n)Stack Overflow

版权声明：本文标题：python - Can I solve this in O(n)? - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1741643372a2390048.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。