BitMap初探-白红宇

BitMap初探

阅读量：4159 次

发布时间：2019-05-26

本文共 2954 字，大约阅读时间需要 9 分钟。

from:

问题：如果要你用最小的空间，将一个正整数序列{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位数字，统计不同号码的个数。

转载地址：http://dkbxi.baihongyu.com/

你可能感兴趣的文章