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

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] 的包含范围内。所以要返回的答案是计数数组 [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 个测试用例中超时，而 returns 个剩余失败测试用例的错误结果。不幸的是，服务器不提供失败的测试用例列表，所以我无法适应这种情况的逻辑。目前，我想不出任何替代策略来解决这个问题。可以

Answer 1

def jobOffers(scores, lowerLimits, upperLimits):
    return [
        len([
            i if i >= lowerLimits[i] and i<= upperLimits[i]
            for i in range(len(lowerLimits))
        ])
    ]

简而言之，dummy 不是布尔值，当为空时可能会计算为 false。我假设您的脚本仅适用于空数组和限制为 1 的数组？

Answer 2

def jobOffers(scores, lowerLimits, upperLimits):
    pairs = list(zip(lowerLimits, upperLimits))

    result = []
    for x in range(len(pairs)):
        u = pairs[x][0]
        l = pairs[x][1]
        a = [x for x in scores if x in range(u, l + 1)]
        result.append(len(a))

    return result

还有哪些测试用例？希望这有帮助。

Answer 3

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

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

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

Optimize algorithm for determining qualifying score from a predefined range

python

algorithm

optimization

computer-science