克服 python 代码的 TLE(超出时间限制)错误
Overcome TLE (Time Limit Exceeded) Error for python code
我在 GeeksforGeeks 上尝试过代码,提交时出现 TLE 错误。
这里是问题:
给极客一个长度为 n 的 nums 数组和两个整数 x 和 y。极客有兴趣找到 (i,j) 对的总数,使得 x <= a[i]*a[j] <= y (1<=i
帮助极客找出此类对的总数。
示例 1:
Input: nums[] = {5,3,7,9,7,9,7,7},
x = 7, y = 19
Output: 1
Explanation: There is only one pair which
satisfies the given conditions. The pair is
(1,2).
示例 2:
Input: nums[] = {3,5,5,2,6},
x = 8, y = 13
Output: 3
Explanation: Pairs which satisfiy the given
conditions are (2,4), (3,4), (4,5).
约束条件:
1<=n<=10^4
1<=nums[i]<=10^4
1<=x<=y<=10^8
这是我的代码:
class Solution:
def TotalPairs(self, nums, x, y):
count = 0
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if x <= nums[i]*nums[j] <= y:
count += 1
return count
#{
# Driver Code Starts
if __name__ == '__main__':
T=int(input())
for i in range(T):
n, x, y = map(int, input().split())
nums = list(map(int, input().split()))
obj = Solution()
ans = obj.TotalPairs(nums, x, y)
print(ans)
# } Driver Code Ends
提交后输出:
运行时错误:
运行时错误超过时间限制
您的程序花费的时间超过预期。
预计时限 7.60 秒
提示:请优化您的代码并重新提交。
通过使用组合,我们可以将 O(n^2) 减少到 O(n)。试试这个:
from itertools import combinations
import math
class Solution:
def TotalPairs(self, nums, x, y):
count = 0
_x = [a[0] * a[1] for a in list(combinations(nums, 2))]
for i in _x:
if x <= i <= y:
count += 1
return count
编辑:您也可以使用lru_cache
来减少执行时间
from itertools import combinations
import math
from functools import lru_cache
import functools
import time
class Solution:
def ignore_unhashable(func):
uncached = func.__wrapped__
attributes = functools.WRAPPER_ASSIGNMENTS + ('cache_info', 'cache_clear')
@functools.wraps(func, assigned=attributes)
def wrapper(*args, **kwargs):
try:
return func(*args, **kwargs)
except TypeError as error:
if 'unhashable type' in str(error):
return uncached(*args, **kwargs)
raise
wrapper.__uncached__ = uncached
return wrapper
@ignore_unhashable
@lru_cache(maxsize = 128)
def TotalPairs(self, nums, x, y):
count = 0
_x = [a[0] * a[1] for a in list(combinations(nums, 2))]
for i in _x:
if x <= i <= y:
count += 1
return count
你有一个 O(N^2) 的解决方案。
这是我认为您可以做的事情,因为毕竟这是一个练习,所以无需尝试放弃大部分代码。
本质上,对于数组中的每个数字 num
,
您需要找出数组中有多少个数字在 [ceil(x/num), floor(y/num)]
.[=30= 范围内]
举个例子,如果 x = 7 和 y = 19,并且说 num = 2。
那么满足条件的最小乘积为8,即num * ceil(x/num) = 2 * ceil(7/2) = 4
最大乘积同样是18,即num * floor(y/num) = 2 * floor(19/2) = 18
。
因此对于 2,您需要列表中位于 [4, 9] 范围内的数字。
这是否提示您应该做什么?
你先对数组进行排序。
然后对于每个 num:
1)你找到ceil(x/num)和floor(y/num)的索引,使用二进制搜索
2)对数将是两个索引的差值+ 1.
这样做的复杂性是,你需要 O(NlogN) 时间来排序,然后你 运行 遍历所有需要 O(N) 时间的数字,对于每个数字你执行两个二进制搜索操作,所以这是 O(NlogN + 2*NlogN) = O(NlogN)
我在 GeeksforGeeks 上尝试过代码,提交时出现 TLE 错误。
这里是问题:
给极客一个长度为 n 的 nums 数组和两个整数 x 和 y。极客有兴趣找到 (i,j) 对的总数,使得 x <= a[i]*a[j] <= y (1<=i
示例 1:
Input: nums[] = {5,3,7,9,7,9,7,7},
x = 7, y = 19
Output: 1
Explanation: There is only one pair which
satisfies the given conditions. The pair is
(1,2).
示例 2:
Input: nums[] = {3,5,5,2,6},
x = 8, y = 13
Output: 3
Explanation: Pairs which satisfiy the given
conditions are (2,4), (3,4), (4,5).
约束条件:
1<=n<=10^4
1<=nums[i]<=10^4
1<=x<=y<=10^8
这是我的代码:
class Solution:
def TotalPairs(self, nums, x, y):
count = 0
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if x <= nums[i]*nums[j] <= y:
count += 1
return count
#{
# Driver Code Starts
if __name__ == '__main__':
T=int(input())
for i in range(T):
n, x, y = map(int, input().split())
nums = list(map(int, input().split()))
obj = Solution()
ans = obj.TotalPairs(nums, x, y)
print(ans)
# } Driver Code Ends
提交后输出:
运行时错误:
运行时错误超过时间限制
您的程序花费的时间超过预期。
预计时限 7.60 秒
提示:请优化您的代码并重新提交。
通过使用组合,我们可以将 O(n^2) 减少到 O(n)。试试这个:
from itertools import combinations
import math
class Solution:
def TotalPairs(self, nums, x, y):
count = 0
_x = [a[0] * a[1] for a in list(combinations(nums, 2))]
for i in _x:
if x <= i <= y:
count += 1
return count
编辑:您也可以使用lru_cache
来减少执行时间
from itertools import combinations
import math
from functools import lru_cache
import functools
import time
class Solution:
def ignore_unhashable(func):
uncached = func.__wrapped__
attributes = functools.WRAPPER_ASSIGNMENTS + ('cache_info', 'cache_clear')
@functools.wraps(func, assigned=attributes)
def wrapper(*args, **kwargs):
try:
return func(*args, **kwargs)
except TypeError as error:
if 'unhashable type' in str(error):
return uncached(*args, **kwargs)
raise
wrapper.__uncached__ = uncached
return wrapper
@ignore_unhashable
@lru_cache(maxsize = 128)
def TotalPairs(self, nums, x, y):
count = 0
_x = [a[0] * a[1] for a in list(combinations(nums, 2))]
for i in _x:
if x <= i <= y:
count += 1
return count
你有一个 O(N^2) 的解决方案。
这是我认为您可以做的事情,因为毕竟这是一个练习,所以无需尝试放弃大部分代码。
本质上,对于数组中的每个数字 num
,
您需要找出数组中有多少个数字在 [ceil(x/num), floor(y/num)]
.[=30= 范围内]
举个例子,如果 x = 7 和 y = 19,并且说 num = 2。
那么满足条件的最小乘积为8,即num * ceil(x/num) = 2 * ceil(7/2) = 4
最大乘积同样是18,即num * floor(y/num) = 2 * floor(19/2) = 18
。
因此对于 2,您需要列表中位于 [4, 9] 范围内的数字。
这是否提示您应该做什么?
你先对数组进行排序。
然后对于每个 num:
1)你找到ceil(x/num)和floor(y/num)的索引,使用二进制搜索
2)对数将是两个索引的差值+ 1.
这样做的复杂性是,你需要 O(NlogN) 时间来排序,然后你 运行 遍历所有需要 O(N) 时间的数字,对于每个数字你执行两个二进制搜索操作,所以这是 O(NlogN + 2*NlogN) = O(NlogN)