一個小程序,求大神們幫個忙

CSDN問答 2022-01-07 12:49:52 阅读数:450

程序 大神

時間複雜度必須不能大於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²)方法開始,然後改進你的算法

考慮使用排序、滑動窗口、二分搜索或這些方法的組合來减少時間複雜性

考慮一種改變數字比特置(即排序)的方法,同時維護對它們最初所在的列錶中的比特置(索引)的引用

 

 

 




采納答案:

二分檢索,時間複雜度為O(nlogn)。 

排序時間複雜度O(nlogn), 二分查找每次左側O(logn), 每次右側O(logn),總複雜度O(nlogn + nlogn+nlogn)=O(nlogn).

from typing import Listimport bisectdef 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


其他答案2:

贊詳細的介紹, 你自己能做到哪個程度呢?

版权声明:本文为[CSDN問答]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071249520295.html