สมมติว่าเรามีรายการตัวเลขสองรายการคือ nums1 และ nums2 และยังมีเลขสองตัวล่างและตัวบน เราต้องหาจำนวนคู่ (i, j) ที่ต่ำกว่า ≤ nums1[i]^2 + nums2[j]^2 ≤ บน
ดังนั้น หากอินพุตเป็น nums1 =[5, 3, 2] nums2 =[8, 12, 6] ต่ำกว่า =10 บน =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
- ม :=ขนาดของ nums2
- ถ้า n> m แล้ว
- สลับ nums1 และ nums2
- สลับ n และ m
- nums2 :=เรียงลำดับรายการ nums2
- res :=0
- สำหรับแต่ละ e1 ใน nums1 ทำ
- st :=ออกจากตำแหน่งมากที่สุดเพื่อแทรก (ด้านล่าง - e1) ลงใน nums2 เพื่อให้องค์ประกอบถูกจัดเรียง
- en :=ตำแหน่งขวาสุดที่จะแทรก (บน - e1) ลงใน nums2 เพื่อให้องค์ประกอบถูกจัดเรียง
- นับ :=en - st
- res :=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
