题目是这样的:给定10亿+个int型数,要求找出重复出现的数字,并输出。(前提是在32位的机器上)
首先,对题目进行认识,如果给定的int型数据很少的话,筛选数据的一般方法是直接建立整型数组存入数据,再利用冒泡或者其他排序方式进行排序就可以很容易筛选出重复的。
然后,要判断机器运算的范围究竟是多大。32位的机器,内存有2的32次方bit,换算成GB是4G,然而实际计算机能用到的不到2G。。。10亿个int,每个int等于4个byte,1个byte等于8个bit,如果全部导入内存的话需要的空间将近30G,远远超出计算机的计算范围。
所以,要将int型数转化之后才能导入内存。计算机内的最小存储单位是bit,如果把数字全存到bit数组里会多大呢?计算之后发现用不了1G,所以可以尝试。用bit数组的下标来记录数字,因为bit只有0和1,所以可以让bit做标志位,初值为0,当该下标的数出现时变为1,当已经为1时证明该下标的数已出现过,one by one的判断。
例如要找的数是100,只需判断bit[100]为0还是1。
然而,代码能开的最小数组是byte,开不了bit的。所以建立byte数组后需要先找到要找的数(bit位)在byte数组中的位置,把该数展开为8位的bit,将用到的位提取出来,对该位上的符号进行判断和处理。
例如还是找100,100/8=12余4,即要找的"bit[100]"其实就在byte[12]中(因为从byte[0]开始),将byte[12]按位展开,得到范围为0-7的8位字符,假设得到的是"00000000",因为余数是4,所以第4位就变为1(从第0位开始),变成"00001000"。
找“bit数组”中的位置就变成找byte数组中的位置(下标)和该位置 按位 展开后某一位的位置。用要找的数除以8,商就是byte数组的下标,余数就是8位中的位置。
至于将byte展开为bit的方法可以自己按位运算写一个方法也可以直接调用如下方法:
String string = Integer.toBinaryString(byte[n]);
这个方法可以将10进制数转化为2进制字符串。然后就可以从字符串中提取当前所需要的位进行操作。具体操作如下代码,如果该位为1即已出现,输出;如果该位为0说明第一次出现,赋值为1。
char[] c=new char[8]; for (int j = 0; j <8; j++) { c[j]=string.charAt(j); } if(c[yu]=='1'){ System.out.println(a[i]+"已出现"); } else{ c[yu]='1'; }
对位运算过后因为要保存数据,所以更改过的位要重新写入byte数组中 。
String st=""; for(int m=0;m<8;m++){ st=st+c[m]; } bytes[zheng]=(byte) Integer.parseInt(st, 2);
另外要注意的一点是因为我们用java写的代码,java中byte是有符号的。
在把byte转展开为2进制数时,如果数展开不足8位,及为较小正数时,系统不会自动左补零补够8位。
在把string的8位当做2进制转成byte时,因为是强制转型,当该数为负时会变成32位,左边全部是1。
具体解决方案如下:
0不够就左补0,为负时就截取最后8位。
while(string.length()<8){//为正小于八位时左补零 string="0"+string; } while(string.length()>9){//为负大于八位截取最后八位 string=string.substring(24,32); }
最后,所有要找的数全部由随机产生。
完整代码如下:
package com.test.myNum; import java.util.Random; public class test { public static void main(String[] args) { byte[] bytes=new byte[170000000]; Random random=new Random(); int a[]=new int[10000000]; int zheng,yu,flag=0; for(int i=0;i<1000000;i++){ a[i]=random.nextInt(1000000000); zheng=a[i]/8; yu=a[i]%8; String string = Integer.toBinaryString(bytes[zheng]); while(string.length()<8){//为正小于八位时左补零 string="0"+string; } while(string.length()>9){//为负大于八位截取最后八位 string=string.substring(24,32); } char[] c=new char[8]; for (int j = 0; j <8; j++) { c[j]=string.charAt(j); } if(c[yu]=='1'){ System.out.println(a[i]+"已出现"); flag++; } else{ c[yu]='1'; } String st=""; for(int m=0;m<8;m++){ st=st+c[m]; } System.out.println(st); bytes[zheng]=(byte) Integer.parseInt(st, 2);// System.out.println(a[i]); } System.out.println("所有数字共重复出现"+flag+"次"); } }
相关推荐
1016:整型数据类型存储空间大小 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 34014 通过数: 23679 【题目描述】 分别定义int,short类型的变量各一个,并依次输出它们的存储空间大小(单位:字节)。 【输入】 ...
(以下讨论,针对32位的计算机系统。。) 问:int型数据占几个字节?答:4字节。...我们可以从3个角度观察这4个字节:(1) 整体看,是一个int型数据;(2) 分成2部分看,是两个短整型数据;(3)
这种类型的对象可以存储10个20~80之间的整数,即他的内部有一个整型数组存储数据。编程: (1) 判断两个inergerSet类对象S1和S2是否相等。提示:集合相等的前提是所有元素相等。 (2) 输出两个集合对象的交集。 ...
超长整型数据的存储与运算C代码
C做的超长整型数据存储与运算代码,加减乘除四则运算
因此,我们来学习一下Android的另外一种存储方式,SharedPreferences存储,它是一种数据持久化的方式,它比文件存储更加简单易用。 将数据存储到SharedPreferences中 不同于文件存储的方式,SharedPreferences是使用...
通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值解释成关键字所在元素的存储地址,这种存储方式称为散列存储。其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也...
整型数据的溢出说明。介绍了C语言中关于整型数据溢出的相关知识,适合于初学者的理解应用。
已知head为单链表的表头指针,链表中存储的都是整形数据,实现下列运算的递归算法: (1)求链表中的最大值。 (2)求链表中的结点个数。 (3)求所有整数的平均值。
以C++类的方式实现整型元素堆栈(stack)数据结构。链栈支持如下基本操作或功能:构造空栈;销毁栈;清除栈;判断栈是否为空;求栈长度;返回栈顶元素;插入栈顶元素;弹出删除栈顶元素;遍历打印栈元素。
小端对齐和大端对齐都是计算机中数据存储的一种方式。 所有的指针类型存储的都是内存地址,内存地址都是一个无符号16进制整型数。 指针间接赋值 两个变量:普通变量、指针变量 建立关系 指针变量=&普通变量 通过 *...
输出byte型的整型的数据范围的最大值和最小值;最大值进行+1时将会变成最小值,其内部是一个循环过程,也就是数据溢出
有的人写出来的程序效率很高,有的人却用复杂的方法来解决一个简单的问题。 当然,程序设计水平的提高仅仅靠看几本程序设计书是不行的。只有多思索、 多练习,才能提高自己的程序设计水平;否则,书看得再多,提高也...
C++数据类型及取值范围 1.基本数据类型: ①字符类型:char(字符型) 例:‘A’,’b’ ②整数类型:int(整型) 例:4563, 234, 885634 ③浮点类型:float(单精度型)、double(双精度型) 例:3.1456 , 0.9e12 ④空值...
1.1 数据类型概览 数据类型算是一种字段约束,它限制每个字段能存储什么样的数据、能存储多少数据、能存储的格式等。MySQL/MariaDB大致有5类数据类型,分别是:整形、...数据类型限定范围的方式有两种:一是严格限定
根据占用内存空间大小的不同,可将整型变量分为4种类型。 2-2 整型变量 整型数据类型 取 值 范 围 存储字节数 short [int] -32 768~32 767 即-215~(215-1) 2 int -32 768~32 767 即-215~(215-1) 2 long [in
16进制与10进制数据转换工具,主要用于程序读写PLC,单片机等数据时读取的16进制数据转换成10进制的数,解决初学者的疑惑,数据在单片机或PLC中存储时是以bit、字节为单元存储的,不管是整型数还是浮点数,最终都是...
仿真环境下,将KEIL中的内存数据导出到excel。 利用excel的公式将数据解析为需要的整型数据。 利用excel图表展示数据图形。
数据结构线性表操作的一个实验: 实验要求 顺序和链式存储的线性表的创建、获取元素、插入和删除元素等基本操作的实现。 题目要求: 输入:一组整型数据A,一组...要求:A和B使用两种存储方式:顺序存储和链式存储。