问题是这样的:如何存储5亿个正整数,并对这些数据进行排重。
直接用一个长度为5亿的int型数组存起来?这显然是不可能的,让我们来计算一下:
一个int型数据占用4byte,5亿个正整数也就是1.6*10^10bit,约为16G,16G的数据全存在内存里,内存显然不够用。那么,如何才能缩小占用空间呢?
再回到问题上看看,问题要求对数据进行排重,在用int存储的情况下,这5亿个数据的范围也就是0-2^31,排重的结果不过就是0到2^31的每一个数值都最多只有一个数存在。约定用1表示有这个数,0表示没有这个数,如此一来就可以用一个bit来表示一个数了。
解决方法如下:建立一个长度为2^28的byte型数组,数组中每一个byte每一位的1或0就代表了数据的存在与否。
在这个题目中,可以认为,我们是从数据流中接收到5亿个数据的。每收到一个数据,就判断它在byte数组中是否存在,若不存在,这把代表这个数据的那一位由0改为1。
代码如下:
//创建一个长度为2^28的byte数组
byte bytes[] = new byte[(int)Math.pow(2, 28)];
int i;//表示数组的第几位
int j;//表示一个byte数据的第几位
int b;//bytes[i]无符号转化后的int数值
int a;//bytes[i]的第j为数值
/**
* 保存出输入流中读到的数据
* @param x 从输入流中获得的正整数
*/
public void paichong(int x){
i = x/8;//一个byte可以存8个数
j = x%8;
this.isExist(x);//判断该数是否已经出现过
if(a==0){//若没有出现过,这把这一位改为1
if(j==7){//若为最高为,直接加2^7最高会变成1,但是其他位也会发生变化
bytes[i] -= 2*bytes[i];
}else bytes[i] += (int)Math.pow(2, j);
}
}
/**
* 判断x是否曾经出现过
* @param x
*/
private void isExist(int x) {
b = bytes[i];
if(bytes[i]<0){
b = (int)(-bytes[i])+128;
}else b = bytes[i];
//类似四位数的位数获得方法
a = b/(int)Math.pow(2, j)%(int)Math.pow(2, 7-j);
}
}
- 大小: 4.4 KB
分享到:
相关推荐
1017:浮点型数据类型存储空间大小 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 27763 通过数: 22417 【题目描述】 分别定义float,double类型的变量各一个,并依次输出它们的存储空间大小(单位:字节)。 ...
Android获取储存信息以及内存信息可以用adb命令查看。... * 获取手机内存总大小 * @return */ public static String getTotalMemorySize() { try { FileReader fr = new FileReader(FILENAME_PROC_ME
1016:整型数据类型存储空间大小 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 34014 通过数: 23679 【题目描述】 分别定义int,short类型的变量各一个,并依次输出它们的存储空间大小(单位:字节)。 【输入】 ...
1017:浮点型数据类型存储空间大小 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 27763 通过数: 22417 【题目描述】 分别定义float,double类型的变量各一个,并依次输出它们的存储空间大小(单位:字节)。 ...
Unity调用Android查看内存信息,在android上面运行时候可查看fps,系统内存大小,系统可用内存大小,当前App占用内存
前言 本文主要介绍了关于MongoDB... 虚拟内存对于进程来说,是一个物理内存的抽象,寻址空间大小为2^64 操作系统通过mmap来把进程所需的所有数据映射到这个地址空间(红线),然后再把当前需要处理的数据映射到物理内存
操作系统可变分区存储管理方式的内存分配和回收,可变分区调度算法有:最先适应分配算法,最优适应分配算法,最坏适应算法 用户提出内存空间的申请;系统根据申请者的要求,按照一定的分配策略分析内存空间的使用情况,...
Android通过IPackageStatsObserver.aidl 、PackageStats.aidl两个AIDL文件获取第三方应用的占用大小,包括缓存、数据、应用大小,经验证和手机设置里面显示的大小完全一致。。。。。。如果还需要其他比如清除缓存之...
内存存储:程序在运行时使用内存来存储数据,包括栈内存和堆内存。栈内存用于存储局部变量、函数调用信息等,而堆内存用于动态分配内存空间。 外部存储:数据也可以被存储在硬盘、数据库或者其他外部设备上。这些...
【题目】内存中的行列结构的数据集,存在主键 k,求 TopN 算法 上述题目在多核环境下的优化 数据集大小为 1TB,分布规律未知。存储在某存储服务上,以 get(min_k, max_k) 接口获取数据,求多台服务器的计算方案 原题...
在linux系统中,查看内存条个数,及每根内存的大小,可以使用dmidecode命令。 如下: #dmidecode | grep -A16 Memory Device$ 输出结果: Memory Device #存储设备 Array Handle: 0x1000 #阵列处理 Error ...
用txt文件存储如下数据:内存总大小、进程数据(到达时间、结束时间、所需内存大小) (2) 运行过程 程序先读入初始txt文档,获得数据;然后根据数据的内容来模拟操作系统进行内存的分配与回收过程; 要求程序能够给...
用txt文件存储如下数据:内存总大小、进程数据(到达时间、结束时间、所需内存大小) (2) 运行过程 程序先读入初始txt文档,获得数据;然后根据数据的内容来模拟操作系统进行内存的分配与回收过程; 要求程序能够...
void *malloc(long numbytes):该函数负责分配 numbytes 大小的内存,并返回指向第一个字节的指针。 void free(void *firstbyte):如果给定一个由先前的 malloc 返回的指针,那么该函数会将分配的空间归还给进程...
查看当前数据库中每个表所占字节(空间)大小
系统从磁盘读取数据到内存时是以磁盘块(block)为基本单位的,位于同一个磁盘块中的数据会被一次性读取出来,而不是需要什么取什么。 InnoDB存储引擎中有页(Page)的概念,页是其磁盘管理的最小单位。InnoDB存储...
今天小编就为大家分享一篇python 基本数据类型占用内存空间大小的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
找不到在Android手机的内存卡重要数据?不要惊慌。 Tenorshare Card Data Recovery 是一个卡存储数据恢复工具,旨在恢复已删除或丢失的照片,视频,音乐,Word文档,PDF文件等,从Android手机中,Windows手机,数码...
java计算机硬盘大小转换(B,KB,MB,GB,TB,PB之间的大小转换) java 硬盘大小转换 数据转换 内存转换 存储大小转换
虚拟内存设置不当也可能导致出现内存不足问题,一般情况下,虚拟内存大小为物理内存大小的2倍即可,如果设置得过小,就会影响系统程序的正常运行。重新调整虚拟内存大小以WinXP为例,右键点击“我的电脑”,选择...