from: http://www.cnblogs.com/blue-cherry/archive/2012/01/12/2320854.html
问题：如果要你用最小的空间，将一个正整数序列{1，2，3，5，8}排序。在N的复杂度内完成，你会怎么做？注意到木有：该正整数序列全部为非负数，且无重复元素
这里，介绍一种新的思路：用位图或位向量来表示集合。在本图中，我们可以用9个bit来表示所有小于9的非负整数集合。上图：
咦？你不是说了是用位来存储的吗？位不是只有0和1两个状态吗，嗯，是的。所以，实际的存储状态是（上面的图只是为了让大家看得更直观）：
嗯，说白了，申请的这九个位，从左到右分别要存储：[0,1,2,3,4,5,6,7,8]。如果该数字在在，则将相应位置为1，否则，置0。
1）用BitMap实现的排序：
/**
* @param arr
* the array to be sorted
* @return
* the sorted array
* @throws DuplicateElement
* */
public int[] sort(int arr[]) throws DuplicateElement {
byte[] bitMap = new byte[max(arr) + 1];
int[] sorted = new int[arr.length];
// 将数组所有元素初始化为0
for (int i = 0; i < bitMap.length; i++) {
bitMap[i] = 0;
}
for (int i = 0; i < arr.length; i++) {
int value = arr[i];
// 增加了对重复元素的判断
if (bitMap[value] == 1) {
throw new DuplicateElement("duplicate element!");
}
bitMap[value] = 1;
}
// 依次将元素存储
int j = 0;
for (int i = 0; i < bitMap.length; i++) {
int value = bitMap[i];
if (value == 1) {
sorted[j++] = i;
}
}
return sorted;
}
// return the max value of a array
private int max(int array[]) {
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (max <= array[i]) {
max = array[i];
}
}
return max;
}
简单吧，更重要的是：时间复杂度只有N。
2）用BitMap判断重复元素
通常的场景为：给定一个长度为N的数组，其中每个元素的取值范围都是1到N。判断数组中是否有重复的数字。（有木有觉得很眼熟，嗯，一道常见的面试题目）
// 判断是否在重复元素
// 复杂度： N
public boolean idDuplicate(int arr[]) {
boolean duplicate = false;
byte[] bitMap = new byte[max(arr) + 1];
// 将数组所有元素初始化为0
for (int i = 0; i < bitMap.length; i++) {
bitMap[i] = 0;
}
for (int i = 0; i < arr.length; i++) {
int value = arr[i];
// 增加了对重复元素的判断
if (bitMap[value] == 1) {
duplicate = true;
}
bitMap[value] = 1;
}
return duplicate;
}
3）用BitMap判断一个元素是否在在于一个数组中
// 判断某个元素a是否在在
public boolean isExist(int arr[], int a) throws DuplicateElement {
boolean exist = false;
byte[] bitMap = new byte[max(arr) + 1];
// 将数组所有元素初始化为0
for (int i = 0; i < bitMap.length; i++) {
bitMap[i] = 0;
}
for (int i = 0; i < arr.length; i++) {
int value = arr[i];
// 没有对重复元素的判断，也就是说，这里，允许arr里面有重复元素在在
bitMap[value] = 1;
}
if (bitMap[a] == 1) {
exist = true;
}
return exist;
}
4）BitMap优势之海量数据存储
8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==12.4MBytes，这样，就用了小小的12.4M左右的内存表示了所有的8位数的电话）
思考题：
2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。