使用bitmap实现对一千万个无重复的正整数(范围1~1亿)快速排序
发布时间:2020-12-14 04:40:56 所属栏目:大数据 来源:网络整理
导读:1 Bytes(字节) == 8 bit1 KBytes == 1024 Bytes 思路: 1)申请长度为1亿的保存二进制位的数组 a, 2)通过位运算,将整数做为索引,将数组a对应的索引位置为1。 3)重复步骤2,直到最后一个整数放到数组中 4)从头开始遍历数组a,将值为1的索引id打印出来。
1 Bytes(字节) == 8 bit 1 KBytes == 1024 Bytes 思路: python 提供了bytearray这个动态的字节数据,以下代码就用bytearray实现 class Bitmap: def __init__(self,num_bits:int): self._num_bits = num_bits self._bytes = bytearray(num_bits // 8 +1) def setbit(self,k:int) ->None: if k > self._num_bits or k < 1: return None # 通过位左移和 或运算可以将对应的bit置为1 self._bytes[k//8] |= (1<<k %8) def getbit(self,k:int)->Optional[bool]: if k > self._num_bits or k < 1: return return self._bytes[k // 8] & (1 << k % 8) != 0 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- OpenRTMFP/Cumulus Primer(2)用Lua编写HelloWorld应用扩展
- [VB.NET]寻求FpSpread学习资料
- 如何在Perl的DBI中使用占位符来实现可变参数SQL函数?
- 在Delphi中是否有* SysUtils.Format *的逆函数
- java – CreateProcess error = 2,系统找不到Roo中指定的
- java – REST服务没有在Spring中使用Spring和Maven注册
- Lua和C++交互总结(很详细)
- bzoj 4802 欧拉函数 (pollardrho大数质因数分解)
- 大数相加(不开辟额外空间)
- [HDU 2817]A sequence of numbers-大数