python - 有效地计算一个列表中的元素数量少于其他列表中的元素

Question

这是我的测试，但时间已经过去了，我很想知道答案

我有两个清单

first_list = [2, 10, 5, 4, 8]
second_list = [3, 1, 7, 8]

我想计算first_list小于second_list like中每个元素的元素数量

2       < 3 ans 1
_       < 1 ans 0
2, 5, 4 < 7 ans 3
2,5,4,8 < 8 ans 4

最后返回列表[1,0,3,4]

count = []
sorted_list = sorted(first_list)
for i in second_list:
    c = 0
    for j in sorted_list:
        if j <= i:
            c += 1
        else:
            break
    count.append(c)

这是我最优化的方法，但得到了code stopped due to runtime error.

标签： python

Answer 1

您可以大大提高大型列表的执行速度。首先对您搜索的列表进行排序：

a = [2, 4, 5, 8, 10]
b = [3, 1, 7, 8]

现在，对于 的每个元素b，对 进行二分搜索a，返回该值适合的索引a。该索引告诉您有多少元素a小于该值。

对列表进行排序是O(n log n)；搜索是O(log n)。您之前的搜索是O(n)（即较慢）。

如果您想进一步改进这一点，也可以对您的b列表进行排序（但请记住原始顺序，以便您知道答案的归属）。从列表中间开始b；找到那个元素。a现在在该点拆分列表；进一步的搜索将只落入一个分区或另一个分区。还要拆分b列表，这样您就知道要使用哪个部分a。对每个新分区继续该过程。