python - 优化用于从预定义范围内确定合格分数的算法

Question

问题:
给你一个分数列表(一维数组)(一些数字)。
您将获得另外两个列表:
lowerLimits :包含下限值的列表
upperLimits :包含上限值的列表

您的任务是找出有多少分数落在每个 (lowerLimit[i], upperLimit[i]) 对的包含范围内。

示例 1:

Inputs:
scores = [1,3,5,6,8]
lowerLimits = [2]
upperLimits = [6]
Output:[3]

解释:scores数组中的三个元素(3,5和6)，落在[2,6]范围内

示例 2:

Inputs:
scores = [4,8,7]
lowerLimits = [2,4]
upperLimits = [8,4]
Output: [3,1]

解释:分数数组中的所有三个元素(4,8 和 7)都落在第一个包含范围 [2,8] 内，只有一个元素(4)落在 [4,4] 的包含范围内。所以要返回的答案是counts数组[3,1]。

到目前为止我尝试了什么算法？

1. Iterate through each lowerLimit - upperLimit pair
2. For this pair check all scores values
3. Repeat step 1 to 2 for all lowerLimit - upperLimit pairs

Python 3 实现

# utility function
def jobOffers(scores, lowerLimits, upperLimits):
    answer = []
    for index, item in enumerate(lowerLimits):
        dummy = []
        for score in scores:
            if score >= lowerLimits[index] and score <= upperLimits[index]:
                dummy.append(score)
        if dummy:
            answer.append(len(dummy))
    return answer

# dummy inputs
scores = [4,8,7]
lowerLimits = [2,4]
upperLimits = [8,4]

print(jobOffers(scores,lowerLimits,upperLimits))

问题:
使用这种蛮力算法，我只能通过 15 个测试用例中的 3 个。事实上，代码在大约 7 个测试用例中超时，并为其余失败的测试用例返回不正确的结果。不幸的是，服务器不提供失败的测试用例列表，所以我无法适应这种情况的逻辑。目前，我想不出任何替代策略来解决这个问题。可以

Answer 1

如果有人感兴趣，我找到了解决方案。我们应该对正确的索引进行二分查找，这样可以节省时间复杂度。这是解决方案:

https://raw.githubusercontent.com/reachsumit/digital-data-scientist-hiring-test-powered-by-hackerrank/master/Question%201/confirmed%20solution%20-%20Python/1.%20solution%20(jobOffers).py