一、给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中 申请512M的内存 判断集合中存在重复是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可取了。
package
com.sitinspring;
/** * 数组重复探测,时间复杂度为O(n) * @author : sitinspring(junglesong@gmail.com) * @date: 2008-6-18-上午03:24:07 */ public class DuplicatedArrayTest { public static void main(String[] args) { int [][] arr = { { 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 } , } ; for ( int i = 0 ;i < arr.length;i ++ ) { System.out.print( " 数组: " ); for ( int temp:arr[i]) { System.out.print(temp + " , " ); } System.out.print( " 中 " ); System.out.print(hasDuplicatedItem(arr[i]) ? " 存在 " : " 不存在 " ); System.out.print( " 重复元素.\n " ); } } /** * 判断整形数组中是否有重复数据,时间复杂度为O(n) * @param arr * @return */ public static boolean hasDuplicatedItem( int [] arr) { // 扫描数组找最大值 int max = arr[ 0 ]; for ( int i = 1 ;i < arr.length;i ++ ) { 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;
/** * 使用位图法进行整形数组排序 * @author 何杨(heyang78@gmail.com) * * @since 2009-2-11 上午08:51:24 * @version 1.00 */ 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) { System.out.print(i + " , " ); } } /** * 使用位图法进行排序 * @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 < newArr.length;i ++ ) { while (newArr[i] > 0 ) { arr[index] = i + min; index ++ ; newArr[i] -- ; } } } } 四、位图法存数据
<>
在 8K 字节的内存空间内,如何存 unsigned short 类型数据? 一般做法: 定义一个数组: unsigned short arrNormal[4096]; 这样做,最多只能存 4K 个 unsigned short 数据。
利用位图法: 定义一个数组: unsigned char arrBit[8192]; 这样做,能存 8K*8=64K 个 unsigned short 数据。
写数据元素:计算待写入数据在 arrBit 存放的字节位置和位位置(字节 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;
// 把数组的 154 字节的 2 位置为 1 unsigned short val = 1<<nBitPos; 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<<nBitPos; 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<<j)) { cout << "arrBit:" << i << " " << j << " " << 8*i+j << endl; } } } 会输出: arrBit:154 2 1234 arrBit:154 4 1236
删除元素:计算待删除元素的字节位置和位位置: arrBit[nBytePos] &= ~(1<< nBitPos); 比如删除 1234 : arrBit[154] &= ~(1<<2);
位图法的缺点: 1. 可读性差 2. 位图存储的元素个数虽然比一般做法多,但是存储的元素大小受限于存储空间的大小。 位图存储性质:存储的元素个数等于元素的最大值。 比如, 1K 字节内存,能存储 8K 个值大小上限为 8K 的元素。(元素值上限为 8K ,这个局限性很大!) 比如,要存储值为 65535 的数,就必须要 65535/8=8K 字节的内存。要就导致了位图法根本不适合存 unsigned int 类型的数(大约需要 2^32/8=5 亿字节的内存)。 3. 位图对有符号类型数据的存储,需要 2 位来表示一个有符号元素。这会让位图能存储的元素个数,元素值大小上限减半。 比如 8K 字节内存空间存储 short 类型数据只能存 8K*4=32K 个,元素值大小范围为 -32K~32K 。 综上所诉:位图法的适用范围很特殊。 五、模拟实现用位图法管理文件存储空间的分配与回收 // bitmap.cpp : Defines the entry point for the console application. |
|