두 개의 숫자 nums1과 nums2 목록이 있다고 가정합니다. 또한 상하 두 개의 숫자가 있습니다. lower ≤ nums1[i]^2 + nums2[j]^2 ≤ upper가 되는 쌍(i, j)의 수를 찾아야 합니다.
따라서 입력이 nums1 =[5, 3, 2] nums2 =[8, 12, 6] lower =10 upper =50과 같으면 쌍이 (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 :=nums2 목록 정렬
- res :=0
- nums1의 각 e1에 대해 다음을 수행합니다.
- st :=요소가 정렬되도록 nums2에 삽입할 가장 왼쪽 위치(하단 - e1)
- en :=요소가 정렬되도록 nums2에 삽입할 가장 오른쪽 위치(위쪽 - e1)
- count :=en - st
- res :=res + count
- 반환 결과
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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