Giả sử chúng ta có hai danh sách các số nums1 và nums2. Và cũng có hai số thấp hơn và trên. Chúng ta phải tìm số cặp (i, j) sao cho dưới ≤ nums1 [i] ^ 2 + nums2 [j] ^ 2 ≤ trên.
Vì vậy, nếu đầu vào là nums1 =[5, 3, 2] nums2 =[8, 12, 6] low =10 upper =50, thì đầu ra sẽ là 2 vì các cặp như (1, 2) và ( 2, 2)
- 10 <=3 ^ 2 + 6 ^ 2 <<50 =10 <=45 <<50
- 10 <=2 ^ 2 + 6 ^ 2 <<50 =10 <=40 <<50
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- thay thế từng phần tử bằng bình phương của nó trong nums1
- thay thế từng phần tử bằng bình phương của nó trong nums2
- n:=kích thước của nums1
- m:=kích thước của nums2
- nếu n> m, thì
- hoán đổi nums1 và nums2
- hoán đổi n và m
- nums2:=sắp xếp danh sách nums2
- res:=0
- đối với mỗi e1 trong nums1, hãy thực hiện
- st:=vị trí ngoài cùng bên trái để chèn (dưới - e1) vào nums2 để các phần tử được sắp xếp
- vi:=vị trí gần nhất bên phải để chèn (upper - e1) vào nums2 để các phần tử được sắp xếp
- count:=en - st
- res:=res + count
- trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[5, 3, 2], [8, 12, 6], 10, 50
Đầu ra
2