首页 > 其他分享 >2563. 统计公平数对的数目

2563. 统计公平数对的数目

时间:2024-09-09 23:47:18浏览次数:12  
标签:upper nums int lo 2563 数对 mid hi 数目

题目链接 2563. 统计公平数对的数目
思路 排序+二分(upper_bound - lower_bound)
题解链接 两种方法:二分查找 / 三指针(Python/Java/C++/Go)
关键点 排序并不影响答案(数对数量未变化)
时间复杂度 \(O(n\log n)\)
空间复杂度 \(O(1)\)

代码实现:

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()

        def upper_bound(val, lo, hi):
            while lo + 1 < hi:
                mid = (lo+hi)//2
                if nums[mid] > val:
                    hi = mid
                else:
                    lo = mid
            return hi
        
        def lower_bound(val, lo, hi):
            while lo + 1 < hi:
                mid = (lo+hi)//2
                if nums[mid] < val:
                    lo = mid
                else:
                    hi = mid
            return hi

        answer = 0
        for j, x in enumerate(nums):
            r = upper_bound(upper-x, -1, j)
            l = lower_bound(lower-x, -1, j)
            answer += r-l
        return answer
Python-标准库
class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        answer = 0
        for j, x in enumerate(nums):
            r = bisect_right(nums, upper-x, 0, j)
            l = bisect_left(nums, lower-x, 0, j)
            answer += r-l
        return answer

标签:upper,nums,int,lo,2563,数对,mid,hi,数目
From: https://www.cnblogs.com/WrRan/p/18405611

相关文章

  • CSS隐藏元素的几种方法,以及他们之间的区别,opacity/visibility/display/rgba函数对比
    文章目录概要displayvisibilityopacitybackground比对概要在网页设计中,我们经常需要将一个元素隐藏或者显示,而需求不同时,不同的隐藏方式也会带来不同的隐藏效果,我们来看看集中隐藏方式的不同。display浏览器不会生成属性为display:none;的元素。dis......
  • Unet改进21:添加AKConv||具有任意采样形状和任意数目参数的卷积核
    本文内容:添加PCONV论文简介摘要。基于卷积运算的神经网络在深度学习领域取得了显著的成果,但标准卷积运算存在两个固有缺陷。一方面,卷积运算被限制在一个局部窗口,不能从其他位置捕获信息,并且其采样形状是固定的;另一方面,卷积核的大小是固定为k×k的,它是一个固定的方形形......
  • python_August(函数对象、功能选择)
    目录python中一切皆对象功能选择函数的嵌套功能选择增加内容版python中一切皆对象#python中一切皆对象#print(self_max)#<functionself_maxat0x0000020E4456CF28>#print(id(self_max))#print(type(self_max))#print(type([1,2]))#print(type(1))#print(type(......
  • 14.STL-内建函数对象
    内建函数对象引入头文件#include<functional>取反negate加法plus大于greater#define_CRT_SECURE_NO_WARNINGS#include<iostream>usingnamespacestd;#include<functional>//内建函数对象头文件#include<vector>#include<algorithm>/*template<......
  • 7-1 素数对猜想(C语言)
    7-1素数对猜想题目参考代码#include<stdio.h>intmain(){ //一、用埃拉托斯特尼筛法,找出所有的素数 intnum[100002]; intN; scanf("%d",&N); for(inti=2;i<N+2;i++)//赋初值为1,表示均为素数 num[i]=1; //把未标记的数的的倍数,全部标记为非素......
  • 【每日一题】LeetCode 1343.大小为K且平均值大于等于阈值的子数组数目(数组、滑动窗口)
    【每日一题】LeetCode1343.大小为K且平均值大于等于阈值的子数组数目(数组、滑动窗口)题目描述给定一个整数数组arr和两个整数k和threshold,要求找出数组中长度为k且平均值大于等于threshold的子数组的数量。输入格式arr:一个整数数组。k:子数组的长度。thres......
  • Dapper传递参数对象时,只支持属性,无法解析字段(出现Parameter '?id' must be defined)
    有的时候使用Dapper执行数据操作时,我们会把模型对象直接作为参数传递进去,但是需要在注意的是!Dapper解析数据是根据属性进行解析的,如果传递的类中使用字段赋值,就会报错 Parameter'?xxx'mustbedefinedclassAAA{publicintID{get;set;}......
  • 【编程基础】亲密数对
    题目描述键盘输入N,N在2至2000之间,求2至N中的亲密数对,就是A的因子和等于B,B的因子和等于A,且A≠B。如48和75是亲密数对。48的因子和为2+3+4+6+8+12+16+24=75,而75的因子和为3+5+15+25=48。输入只有一行,为一个整数N(2<=N<=2000)输出输出若干行,每行两个整数(用一个空格隔开)。样......
  • vue2和vue3生命周期钩子函数对比图
    vue2->vue3触发条件beforeCreate->使用setup()创建时运行created->使用setup()创建时运行beforeMount->onBeforeMount挂载DOM运行mounted->onMounted挂载DOM运行beforeUpdate->onBeforeUpdate响应数据修改时运行......
  • 力扣刷题——3096.得到更多分数的最少关卡数目
    根据题意,假如alice选择完成第i关到第j关,那么bob需要完成第j+1关到第n关,其中i<=j<n。如此可以想到对关卡数组进行预处理,构建一个前缀和数组,保存假如从第0关每关都通过的话,到第i关所得到的分数。通过遍历一次前缀和数组,能够得到每个时刻alice得到的分数和bob得到的分数,当alice获得......