求O(nlogn)复杂度算法：统计列表中≤当前元素的其他元素个数

要把时间复杂度降到O(nlogn)，核心是利用排序+二分查找的组合：

• 排序的时间复杂度是O(nlogn)，之后每个元素的查询操作可以用二分查找在O(logn)时间内完成，整体复杂度就能达到要求。

具体步骤 #

1. 先对原数组list_A进行排序，得到有序数组sorted_A。
2. 针对原数组中的每个元素x：
   • 在sorted_A中找到第一个大于x的元素的位置（用二分查找的右边界），这个位置的数值就等于sorted_A中小于等于x的元素总数。
   • 因为要排除元素自身，所以将这个数值减1，就是list_B对应位置的结果。

代码实现 #

利用Python内置的bisect模块可以快速实现二分查找：

import bisect

def compute_list_B(list_A):
    sorted_A = sorted(list_A)
    list_B = []
    for x in list_A:
        # bisect_right返回第一个大于x的元素索引，即<=x的元素总数
        count = bisect.bisect_right(sorted_A, x)
        list_B.append(count - 1)
    return list_B

# 测试示例
list_A = [111, 192, 171, 391, 91, 142, 31, 373, 493, 468]
list_B = compute_list_B(list_A)
print(list_B)  # 输出: [2, 5, 4, 7, 1, 3, 0, 6, 9, 8]，和示例一致

# 测试原代码中的例子
vettore_A = [1,2,3,4,5,6,7,8,9,0]
vettore_B = compute_list_B(vettore_A)
print(vettore_B)  # 输出: [1,2,3,4,5,6,7,8,9,0]

复杂度说明 #

• 排序操作sorted(list_A)的时间复杂度是O(nlogn)。
• 遍历原数组的n个元素，每个元素调用bisect_right的时间复杂度是O(logn)，总耗时O(nlogn)。
• 两者相加，整体时间复杂度为O(nlogn)，远优于原代码的O(n²)。

内容的提问来源于stack exchange，提问作者kekkodiaz