一个小程序，求大神们帮个忙

Question

时间复杂度必须不能大于nlogn

要用python完成

在这个问题中，你将得到一个整数列表，代表每个玩家在他们的最后一场比赛中持有的股票数量，以及一个整数，代表要检查的范围应该有多宽。使用这些给定的变量，你的目标是找到每个玩家所创造的范围内的玩家数量。

例如，假设给定的列表为[5,1,3,1]，范围变量为2。第一个要处理的参与人在索引0处。他们在最后一场比赛中赢了5支股票。要检查的范围是2高于5所以是7,2低于5所以是3。然后，我们的范围将是[(5-2)，(5+2)]或[3,7]，两端都包括在内。在给定的列表中只有一个值3，所以索引为0的玩家只有1场比赛可用。有关更深入的示例，请查看后面的示例。

您的目标是返回一个包含每个玩家可用对手数量的列表。上面示例的返回列表将是[1,2,3,2]。

2、向列表中添加元素:List[int]， k [int]



stocks_list: List[int]:一个长度为n的Python列表，包含整数，表示每个玩家在最后一场比赛中获得的股票。每个指数代表一个玩家。

k: int: Integer表示用于确定每个玩家所有可用对手的范围

返回:一个长度为n的Python列表，包含整数，包含每个玩家可用对手的数量。

时间复杂度:O(nlog(n))，其中n是玩家数量

保证的条件：

范围k是非负的(可以是正的也可以是零的)

stocks_list可以包含任何整数、负数、正数和0

stocks_list可能包含重复的股票编号

每个测试用例都是保证生成的

例子:

例1:

stocks_list = [5, 1, 3, 2]

k = 1

第一个玩家的股票从指数0[5,1,3,2]到5，范围是1。检查可能的对手的范围将是1低于5和1高于5。因此，取值范围应该是[5 - 1,5 + 1]或[4,6]，两边都要包括。在给定的列表中，没有任何值在查找范围[4,6]内，除了这个玩家。因此，没有人会与这个球员匹配，并且一个0应该被放置在返回列表的索引0处。
第二个玩家的股票从指数1[5,1,3,2]中取1，范围为1。检查可能的对手的范围将是1低于1和1高于1。因此，取值范围应该是[1 - 1,1 + 1]或[0,2]，两边都要包括。在给定的列表中，在查找范围内有一个值[0,2]，但不包括这个玩家。因此，只有一个玩家将与这个玩家匹配，并且1应该被放置在返回列表的索引1处。
第三个玩家的股票是指数2[5,1,3,2]中的3，范围是1。检查可能的对手的范围将是1低于3和1高于3。因此，取值范围应该是[3 - 1,3 + 1]或[2,4]，两边都要包括。在给定的列表中，在查找范围内有一个值[2,4]，但不包括这个玩家。因此，只有一个玩家将与这个玩家匹配，并且1应该被放置在返回列表的索引2处。
最后一个玩家的股票是指数3[5,1,3,2]中的2，范围是1。检查可能的对手的范围将是1低于2和1高于2。因此，取值范围为[2 - 1,2 + 1]或[1,3]，两边都要包含。在给定的列表中，在查找范围内有两个值[1,3]，不包括这个玩家。因此，两个玩家将与这个玩家匹配，一个2应该被放置在返回列表的索引3处。
根据以上结果，每个玩家的可能对手数返回列表为[0,1,1,2]

例2:
stocks_list = [40,22,30,20]

k = 5

第一个玩家的股票是指数0[40,22,30,20]的40，范围是5。检查可能的对手的范围将是5低于40和5高于40。因此，取值范围应该是[40 - 5,40 + 5]或[35,45]，两边都要包括。在给定的列表中，除了这个玩家，在这个查找范围[35,45]内没有任何值。因此，没有人会与这个球员匹配，并且一个0应该被放置在返回列表的索引0处。

第二个玩家的股票是指数1[40,22,30,20]中的22，范围是5。检查可能的对手的范围将是5低于22和5高于22。因此，取值范围应该是[22 - 5,22 + 5]或[17,27]，两边都要包括。在给定的列表中，在查找范围内有一个值[17,29]，但不包括这个玩家。因此，只有一个玩家将与这个玩家匹配，并且1应该被放置在返回列表的索引1处。

第三个玩家的股票是指数2[40,22,30,20]的30，范围是5。检查可能的对手的范围将是5低于30和5高于30。因此，取值范围应该是[30 - 5,30 + 5]或[25,35]，两边都要包括。在给定的列表中，除了这个玩家之外，在这个查找范围[25,35]内没有任何值。因此，没有人会与这个玩家匹配，一个0应该被放置在返回列表的索引2处。

最后一个玩家的股票是指数3[40,22,30,20]的20，范围是5。检查可能的对手的范围将是5低于20和5高于20。因此，取值范围应该是[20 - 5,20 + 5]或[15,25]，两边都要包括在内。在给定的列表中，有一个玩家在寻找范围内[15,25]，但不包括这个玩家。因此，一个玩家将与这个玩家匹配，并且1应该被放置在返回列表的索引3处。

根据以上结果，每个玩家的可能对手数返回列表为[0,1,0,1]

提示:

试着从O(n²)方法开始，然后改进你的算法

考虑使用排序、滑动窗口、二分搜索或这些方法的组合来减少时间复杂性

考虑一种改变数字位置(即排序)的方法，同时维护对它们最初所在的列表中的位置(索引)的引用

 

 

 

Answer 1

二分检索，时间复杂度为O(nlogn)。 

排序时间复杂度O(nlogn), 二分查找每次左侧O(logn), 每次右侧O(logn),总复杂度O(nlogn + nlogn+nlogn)=O(nlogn).

from typing import List
import bisect


def challenger_finder(socket_list: List[int], k:int) ->List[int]:
	n = len(socket_list)
	st = sorted(socket_list)
	ans = []

	for i in range(n):
		left = socket_list[i] - k
		right = socket_list[i] + k
		lk = bisect.bisect_left(st, left)
		rk = bisect.bisect_right(st, right)
		ans.append(rk-lk-1)
	return ans