以尽可能低的时间复杂度，从列表中第一个较小的数字中减去列表中的每个数字

Question

我有一个数字列表，我想从它后面的较小值中减去每个数字，但复杂度尽可能低我有列表 [7, 18 ,5 ,5 ,20 ,9 ,14 ,7 ,19]

7之后的第一个较小的值是5所以它会从5中减去7，对于 18 相同，它是 5 之后的第一个较小的值，因此它将从 5 中减去 18，依此类推。

输出应该是 [2, 13, 5, 5, 11, 2, 7, 7, 19]

我写了一个解决问题的代码，但是用 O(N^2)，但我想知道我是否可以用较低的时间复杂度来解决它

l1=[7,18,5,5,20,9,14,7,19]
l2=[]
for i ,j in enumerate (list1):
     k=0
     for n in list1[i+1:]:
      if n<j:
         l2.append(j-n)
         k=1
         break 
     if k==0:
      l2.append(j)    
print(l2)

Answer 1

用替代数字迭代列表，比较前一个和下一个，如果比较为真，replace/delete 和列表中的 number/numbers。循环直到列表中没有数字。

Answer 2

我不确定这到底有多复杂，但它不是O(n^2)你可以试试这个。您可以使用堆栈。

list1=[7,18,5,5,20,9,14,7,19]
stack = [(0, list1[0])]
res = [0] * len(list1)

for idx, i in enumerate(list1[1:], 1):
    while stack and stack[-1][-1] > i:
        old_idx, old_i = stack.pop()
        res[old_idx] = old_i - i
    stack.append((idx, i))

for idx, i in stack:
    res[idx] = i

print(res)

输出

[2, 13, 5, 5, 11, 2, 7, 7, 19]

在 jupyter 中使用 %%timeit -n 10 -r 10 进行基准测试，增加了输入列表以显示效率。

list1=[7,18,5,5,20,9,14,7,19]
for _ in range(10):
    list1 += list1

这个解决方案

2.06 ms ± 37.1 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)

原码

209 ms ± 2.71 ms per loop (mean ± std. dev. of 10 runs, 10 loops each)

这个解决方案更快。

根据@JérômeRichard 的评论进行编辑，这在线性时间内运行 O(n)。

This is O(n). Here is the proof: you cannot append more element to the stack than the number of element in the input list because of the append. You cannot remove more element from the stack than the number of appended elements. Both pop and append are (amortized) O(1) operations. Then final loop is running in O(n)

为了更好理解的注释版本

list1=[7,18,5,5,20,9,14,7,19] # input list

# create an unbounded stack
# `stack` will have a tuple of elements in the form (index, value)
# add the first element in the input list to the stack along with the index
stack = [(0, list1[0])] # (index, value)

# result list to store the result
# size will be the same as that of the input list `list1`
res = [0] * len(list1)

# start iterating the rest of the elements `list1[1:]` as the first element is already in the stack
# start enumerate index from 1
for idx, i in enumerate(list1[1:], 1):
    """
    how the while loop works
        check if stack is not empty and if the top element in the stack `stack[-1][-1]` is greater than the current element `i`
        if this condition is `True`, it essentially means that `i` is the right most minimum element for the top element in the stack
        stack[-1] is the top element of the stack, so `stack[-1][-1]` will give the value of the top element in the stack
        remember every element in `stack` is a tuple of form (index, value), the value `stack[-1][-1]` is needed to compare, index `stack[-1][0]` is used later
        both these checks are constant time operations `O(1)`.
    """
    while stack and stack[-1][-1] > i:
        # pop the top element and get the old index and old value as `old_idx` and `old_i`
        old_idx, old_i = stack.pop()
        # subtract old element `old_i` with current element `i`
        # `old_idx` is the index where the result of the above operation must be placed
        # assign the result to the `old_idx`
        res[old_idx] = old_i - i

    # add the current element and its index in the stack for comparing that in next iteration
    stack.append((idx, i))

# if there are any elements remaining in the stack then these elements do not have a minimum value to their right
# so just get their index and set the corresponding value in the `res` list, that will be their position
for idx, i in stack:
    res[idx] = i

# result :)
print(res)

以尽可能低的时间复杂度，从列表中第一个较小的数字中减去列表中的每个数字

With lowest possible time complexity , subtract every number in a list from the first lower number after it

python

performance

list

time-complexity