Python Bisect

简介: Python Bisect

bisect是python内置模块,用于有序序列的插入和查找

  • 查找: bisect(array, item)
  • import bisect
  • 若数组a是升序序列
  • 使用总结:


bisect.bisect(a,c):返回数组a中最后一个<=c的索引值+1


若c存在于数组a,bisect.bisect_left(a,c)返回数组a中第一个出现c的索引值


若c不存在于数组a,bisect.bisect_left与bisect.bisect等效


若c存在于数组a,bisect.bisect_right(a,c)返回数组a中最后一个等于c的索引值+1


若c不存在于数组a,bisect.bisect_right与bisect.bisect等效


在查询一个有序的数组中有多少个>(<) c的时候,这个函数效率很高

import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
c.sort()
ans = 0
for i in range(n):
  x=bisect.bisect_left(a,b[i])
  y=len(c)-bisect.bisect_right(c,b[i])
  ans += x*y
print(ans)

8a0aea1067114ce68639977d2c0d8ec6.png

这个代码是可以解决蓝桥杯一道真题:三元递增组,相较于用前缀和,代码量大大化简

前缀和代码:

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[0 for i in range(max(a)+1)]
for i in a:
    ans[i]+=1
x=[0 for i in range(max(a)+1)]
x[0]=a.count(0)
for j in range(1,max(a)+1):
    x[j]=x[j-1]+ans[j]
cns=[0 for i in range(max(c)+1)]
for i in c:
    cns[i]+=1
y=[0 for i in range(max(c)+1)]
y[0]=c.count(0)
for j in range(1,max(c)+1):
    y[j]=y[j-1]+cns[j]
cnt=0
for k in range(n):
    if b[k]-1>len(x)-1:
        p=x[-1]
    elif b[k]-1<0:
        p=0
    else:
        p=x[b[k]-1]
    if len(y)-1<=b[k]:
        q=0
    else:
        q=y[-1]-y[b[k]]
    cnt+=p*q
print(cnt)

掌握一些内置的高效函数,大有裨益!

相关文章
|
算法 索引 Python
Python数据结构与算法(8)---维护有序列表bisect
Python数据结构与算法(8)---维护有序列表bisect
115 0
Python数据结构与算法(8)---维护有序列表bisect
|
算法 Python
Python基础——bisect模块
这个模块对有序列表提供了支持,使得他们可以在插入新数据仍然保持有序。
127 0
|
算法 Python
每周一个 Python 模块 | bisect
bisect 模块,用于维护有序列表。实现了一个算法用于插入元素到有序列表。在一些情况下,这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect 是二分法的意思,这里使用二分法来排序,它会将一个元素插入到一个有序列表的合适位置,这使得不需要每次调用 sort 的方式维护有序列表。
67 0
python之bisect模块, 有序列表插入数据
bisect是python的内置模块, 可以使用它来插入数据, 并且插入的数据不会影响列表的排序, **但是原有列表需要是有序的, 并且不能是倒序**.
|
12天前
|
安全 数据处理 开发者
Python中的多线程编程:从入门到精通
本文将深入探讨Python中的多线程编程,包括其基本原理、应用场景、实现方法以及常见问题和解决方案。通过本文的学习,读者将对Python多线程编程有一个全面的认识,能够在实际项目中灵活运用。
|
6天前
|
设计模式 开发者 Python
Python编程中的设计模式:工厂方法模式###
本文深入浅出地探讨了Python编程中的一种重要设计模式——工厂方法模式。通过具体案例和代码示例,我们将了解工厂方法模式的定义、应用场景、实现步骤以及其优势与潜在缺点。无论你是Python新手还是有经验的开发者,都能从本文中获得关于如何在实际项目中有效应用工厂方法模式的启发。 ###
|
12天前
|
弹性计算 安全 小程序
编程之美:Python让你领略浪漫星空下的流星雨奇观
这段代码使用 Python 的 `turtle` 库实现了一个流星雨动画。程序通过创建 `Meteor` 类来生成具有随机属性的流星,包括大小、颜色、位置和速度。在无限循环中,流星不断移动并重新绘制,营造出流星雨的效果。环境需求为 Python 3.11.4 和 PyCharm 2023.2.5。
|
5天前
|
数据处理 Python
从零到英雄:Python编程的奇幻旅程###
想象你正站在数字世界的门槛上,手中握着一把名为“Python”的魔法钥匙。别小看这把钥匙,它能开启无限可能的大门,引领你穿梭于现实与虚拟之间,创造属于自己的奇迹。本文将带你踏上一场从零基础到编程英雄的奇妙之旅,通过生动有趣的比喻和实际案例,让你领略Python编程的魅力,激发内心深处对技术的渴望与热爱。 ###
|
8天前
|
数据采集 机器学习/深度学习 人工智能
Python编程入门:从基础到实战
【10月更文挑战第24天】本文将带你进入Python的世界,从最基础的语法开始,逐步深入到实际的项目应用。我们将一起探索Python的强大功能和灵活性,无论你是编程新手还是有经验的开发者,都能在这篇文章中找到有价值的内容。让我们一起开启Python的奇妙之旅吧!