马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?立即注册
x
【LetMeFly】2563.统计公平数对的数目:排序 + 二分查找
力扣标题链接:https://leetcode.cn/problems/count-the-number-of-fair-pairs/
给你一个下标从 0 开始、长度为 n 的整数数组 nums ,和两个整数 lower 和 upper ,返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况,则以为它是一个 公平数对 :
- 0 <= i < j < n,且
- lower <= nums + nums[j] <= upper
示例 1:
- <b>输入:</b>nums = [0,1,7,4,4,5], lower = 3, upper = 6
- <b>输出:</b>6
- <b>解释:</b>共计 6 个公平数对:(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。
复制代码 示例 2:
- <b>输入:</b>nums = [1,7,9,2,5], lower = 11, upper = 11
- <b>输出:</b>1
- <b>解释:</b>只有单个公平数对:(2,3) 。
复制代码
提示:
- 1 <= nums.length <= 105
- nums.length == n
- -109 <= nums <= 109
- -109 <= lower <= upper <= 109
解题方法:排序 + 二分查找
要找的是值在肯定范围内的 n u m s [ i ] + n u m s [ j ] nums + nums[j] nums+nums[j],且加法满足互换律( a + b = b + a a+b=b+a a+b=b+a),所以查找结果和元素顺序无关。
所以只需要遍历 n u m s nums nums的下标作为 i i i,并在 i + 1 i+1 i+1到数组末端的范围内查找 j j j的范围,终极累加到答案中即可。
如何确定 j j j的范围? u p p e r _ b o u n d ( u p p e r − i ) − l o w e r _ b o u n d ( l o w e r − i ) upper\_bound(upper - i) - lower\_bound(lower - i) upper_bound(upper−i)−lower_bound(lower−i)或 l o w e r _ b o u n d ( u p p e r − i + 1 ) − l o w e r b o u n d ( l o w e r − i ) lower\_bound(upper - i + 1) - lower_bound(lower - i) lower_bound(upper−i+1)−lowerbound(lower−i)均可。
此中 l o w e r b o u n d ( t ) lower_bound(t) lowerbound(t)黑白递减数组中第一个插入 t t t后数组仍非递减的下标, u p p e r b o u n d ( t ) upper_bound(t) upperbound(t)黑白递减数组中末了一个插入 t t t后数组仍非递减的下标。
- 时间复杂度 O ( n log n ) O(n\log n) O(nlogn),此中 n = l e n ( n u m s ) n=len(nums) n=len(nums)
- 空间复杂度 O ( log n ) O(\log n) O(logn)
AC代码
C++
- /*
- * @Author: LetMeFly
- * @Date: 2025-04-19 15:51:42
- * @LastEditors: LetMeFly.xyz
- * @LastEditTime: 2025-04-19 16:12:44
- */
- /*
- l: first j 满足 nums[j] + nums[i] >= lower | nums[j] >= lower - nums[i]
- r: last j 满足 nums[j] + nums[i] <= upper | nums[j] <= upper - nums[i]
- l: lower_bound(lower - nums[i])
- r: upper_bound(upper - nums[i])
- */
- typedef long long ll;
- class Solution {
- public:
- long long countFairPairs(vector<int>& nums, int lower, int upper) {
- sort(nums.begin(), nums.end());
- ll ans = 0;
- for (int i = 0; i < nums.size(); i++) {
- ans += upper_bound(nums.begin() + i + 1, nums.end(), upper - nums[i]) - lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]);
- // cout << i << ": " << i << "[" << lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]) - nums.begin() << ", " << upper_bound(nums.begin() + i + 1, nums.end(), upper - nums[i]) - nums.begin() << ')' << endl;
- }
- return ans;
- }
- };
复制代码 Python
- '''
- Author: LetMeFly
- Date: 2025-04-19 16:13:37
- LastEditors: LetMeFly.xyz
- LastEditTime: 2025-04-19 16:23:38
- '''
- from typing import List
- from bisect import bisect_left, bisect_right
- class Solution:
- def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
- nums.sort()
- return sum(bisect_right(nums, upper - nums[i], i + 1) - bisect_left(nums, lower - nums[i], i + 1) for i in range(len(nums)))
复制代码 Java
- /*
- * @Author: LetMeFly
- * @Date: 2025-04-19 16:24:08
- * @LastEditors: LetMeFly.xyz
- * @LastEditTime: 2025-04-19 16:37:36
- */
- import java.util.Arrays;
- class Solution {
- private int search(int[] nums, int x, int l) { // search [l, len(nums)) 范围内第一个大于等于x的下标
- int r = nums.length;
- while (l < r) {
- int mid = (l + r) >> 1;
- if (nums[mid] >= x) {
- r = mid;
- } else {
- l = mid + 1;
- }
- }
- return l;
- }
- public long countFairPairs(int[] nums, int lower, int upper) {
- Arrays.sort(nums);
- long ans = 0;
- for (int i = 0; i < nums.length; i++) {
- ans += search(nums, upper - nums[i] + 1, i + 1) - search(nums, lower - nums[i], i + 1);
- }
- return ans;
- }
- }
复制代码 Go
- /*
- * @Author: LetMeFly
- * @Date: 2025-04-19 16:24:24
- * @LastEditors: LetMeFly.xyz
- * @LastEditTime: 2025-04-19 16:43:06
- */
- package main
- import (
- "sort"
- )
- func countFairPairs(nums []int, lower int, upper int) (ans int64) {
- sort.Ints(nums)
- for i, v := range nums {
- l := sort.Search(len(nums), func(x int) bool {return x > i && nums[x] >= lower - v})
- r := sort.Search(len(nums), func(x int) bool {return x > i && nums[x] >= upper - v + 1})
- ans += int64(r - l)
- }
- return
- }
复制代码 同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |