在Python中编写程序查找平方元素在给定范围内的对数
假设我们有两个数字列表nums1和nums2。同时还有两个数字lower和upper。我们必须找到对数(i, j),使得lower ≤ nums1[i]^2 + nums2[j]^2 ≤ upper。
所以,如果输入如下nums1 = [5, 3, 2] nums2 = [8, 12, 6] lower = 10 upper = 50,那么输出将是2,因为对数是(1, 2)和(2, 2)
- 10 <= 3^2 + 6^2 << 50 = 10 <= 45 << 50
- 10 <= 2^2 + 6^2 << 50 = 10 <= 40 << 50
为了解决这个问题,我们将按照以下步骤进行 −
- 在nums1中用它的平方替换每个元素
- 在nums2中用它的平方替换每个元素
- n := nums1的大小
- m := nums2的大小
- 如果n > m,则
- 交换nums1和nums2
- 交换n和m
- 对列表nums2进行排序
- res := 0
- 对于nums1中的每个e1,执行以下操作
- 将(lower – e1)插入nums2以使元素排序,返回最左侧位置的st
- 将(upper – e1)插入nums2以使元素排序,返回最右侧位置的en
- count := en – st
- res := res + count
- 返回res
示例
以下是更好地理解的实现 −
from bisect import bisect_left, bisect_right
def solve(nums1, nums2, lower, upper):
nums1 = [i * i for i in nums1]
nums2 = [i * i for i in nums2]
n, m = len(nums1), len(nums2)
if n > m:
nums1, nums2 = nums2, nums1
n, m = m, n
nums2 = sorted(nums2)
res = 0
for e1 in nums1:
st = bisect_left(nums2, lower - e1)
en = bisect_right(nums2, upper - e1)
count = en - st
res += count
return res
nums1 = [5, 3, 2]
nums2 = [8, 12, 6]
lower = 10
upper = 50
print(solve(nums1, nums2, lower, upper))
输入
[5, 3, 2], [8, 12, 6], 10, 50
输出
2