資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學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 := 對列表nums2進行排序
- res := 0
- 對於nums1中的每個元素e1：
- st := 在nums2中插入(lower - e1)的最左位置，以便元素保持排序。
- en := 在nums2中插入(upper - e1)的最右位置，以便元素保持排序。
- 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
更新於：2021年10月16日
瀏覽量：184
廣告