python - 通过最小化迭代次数改进代码

Question

我有一个练习做得很好，但我正在寻求改进。

在我的代码中，我使用了嵌套循环，我想让它成为 1 个循环，但我无法达到目标。

def main(l1):
    newlist = []
    numbers= max(l1) + 1
    for i in range(0,numbers):
        counter = 0
        for number in l1:
            if number >= i:
                counter += 1
        newlist.append(counter)
    print(newlist)

l1=[1,5,4,3,7,8,9]
main(l1)

它返回 [7, 7, 6, 6, 5, 4, 3, 3, 2, 1] 10 索引(l1 +1 的最大值)

练习的目标是找到 l1 中的最大值，然后测试 range(0,maximumnumber+1) 中的每个数字，

将 l1 中的每个数字与范围内的数字进行比较 (if(number >= number in the range)) 并计算 l1 中的数字大于等于范围内的数字的次数。

我希望它是多么清晰，代码更清晰

Answer 1

这是一个非常简单的改进:

from itertools import accumulate
def one(l1):
    counts = [0] * (max(l1) + 1)
    for n in l1:
        counts[-n - 1] += 1
    return list(accumulate(counts))[::-1]

---

这个版本要复杂得多，但只需两次即可完成所有操作，我认为这是解决此问题的最低要求:

def two(l1):
    counts = []
    for n in l1:
        try:
            counts[n] += 1
        except IndexError:
            counts.extend([0] * (n - len(counts)) + [1])

    total = counts[-1]
    for i in range(-2, -len(counts) - 1, -1):
        total += counts[i]
        counts[i] = total

    return counts

---

两种解决方案分别是 O(n) 和摊销的 O(n)。

您可以通过预分配列表将第二个解决方案修改为 O(n)，但这需要权衡需要对列表进行三次传递。

---

上面两种解决方案的基本思想是，你首先做一个 counting sort , 然后做 running sum从列表的后面开始。