问题是这样的：如何存储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);
}
}
已有 0 人发表留言，猛击->> 这里<<-参与讨论
ITeye推荐