if (arr[i] > max) {
max = arr[i];
}
}
int [] bitArray = new int [max +1 ];
// 按值向新
数组中添值，如value为3则bitArray[3]=1
for ( int value:arr) {
if (bitArray[value] != 0 ) {
// 如果value指向的位置已经不是零，说明之前已经给这一块置1了，立即返回true表示
数组有重复
return true ;
}
else {
// value指向的位置是零,则置为1表示这一位已经有数存在了
bitArray[value] = 1 ;
}
}
return false ;
}
}
输出：
数组: 1 , 2 , 3 , 5 , 3 , 5 , 56 , 534 , 3 , 32 ,中存在重复元素.
数组: 1 , 2 , 3 , 5 ,中不存在重复元素.
数组: 1 , 2 , 3 , 5 , 3 , 5 ,中存在重复元素.
数组: 0 , 0 , 1 , 2 , 3 , 5 , 56 , 534 , 78 , 32 ,中存在重复元素.
package com.heyang;
public class BitmapSorter {
public static void main(String[] args) {
int [] arr = { 1 , 7 , - 3 , 0 , 0 , 6 , 6 , 9 , - 11 } ;
bitmapSort(arr);
for ( int i:arr) {
}
}
/**
* 使用位图法进行排序
* @param arr
*/
public static void bitmapSort( int [] arr) {
int max = arr[ 0 ];
int min = max;
for ( int i:arr) {
if (max < i) {
max = i;
}
if (min > i) {
min = i;
}
}
int [] newArr = new int [max -min + 1 ];
for ( int i:arr) {
int index = i - min;
newArr[index] ++ ;
}
// 重整arr中的元素
int index = 0 ;
for ( int i = 0 ;i
while (newArr[i] > 0 ) {
arr[index] = i + min;
index ++ ;
newArr[i] -- ;
}
}
}
}
四、位图法存数据
在 8K 字节的内存空间内，如何存 unsigned short 类型数据？
一般做法：
定义一个
数组： unsigned shortarrNormal[4096];
这样做，最多只能存 4K 个 unsigned short 数据。
利用位图法：
定义一个
数组： unsigned chararrBit[8192];
这样做，能存 8K*8=64K 个 unsigned short 数据。
rrBit 存放的
字节位置和位位置（字节 0~8191 ，位 0~7 ）
比如写 1234 ，
字节序： 1234/8 = 154; 位序： 1234 &0b111 = 2 ，那么 1234 放在 arrBit 的下标 154 字节处，把该字节的 2 号位（ 0~7）置为 1
字节位置： int nBytePos =1234/8 = 154;
位位置： int nBitPos = 1234 & 7 = 2;
unsigned short val = 1＜
arrBit[nBytePos] = arrBit[nBytePos] |val; // 写入 1234 得到arrBit[154]=0b00000100
此时再写入 1236 ，
字节位置： int nBytePos =1236/8 = 154;
位位置： int nBitPos = 1236 & 7 = 4
.// / 把
数组的 154 字节的 4 位置为 1
val = 1＜
arrBit[nBytePos] = arrBit[nBytePos] |val; // 再写入 1236 得到arrBit[154]=0b00010100
读
数据元素：按位读取 arrBit ，取得位为 1 的字节位置和位位置。元素值为 8*nBytePos + nBitPos
for (i=0; i＜8192; i++)
{
for (j=0; j＜8; j++)
{
if (arrBit[i] & (1＜
{
}
}
}
会输出：
arrBit:154 2 1234
arrBit:154 4 1236
删除元素：计算待删除元素的字节位置和位位置：arrBit[nBytePos] &= ~(1<< nBitPos);
比如删除 1234 ： arrBit[154] &= ~(1<<2);