在海量數(shù)據(jù)中查找出重復出現(xiàn)的元素或者去除重復出現(xiàn)的元素是面試中常考的文圖。針對此類問題，可以使用位圖法來解決。例如：已知某個文件內包含若干個電話號碼，要求統(tǒng)計不同的號碼的個數(shù)，甚至在o（n）時間復雜度內對這些號碼進行排序。
位圖法需要的空間很少（依賴于數(shù)據(jù)分布，但是我們也可以通過一些放啊發(fā)對數(shù)據(jù)進行處理，使得數(shù)據(jù)變得密集），在數(shù)據(jù)比較密集的時候效率非常高。例如：8位整數(shù)可以表示的最大十進制數(shù)值為99999999，如果每個數(shù)組對應于一個bit位，那么把所有的八進制整數(shù)存儲起來只需要：99mbit = 12.375mb.
實際上，java jdk1.0已經(jīng)提供了bitmap的實現(xiàn)bitset類，不過其中的某些方法是jdk1.4之后才有的。
下面我先自己實現(xiàn)一下bitmap 的原理，然后再直接調用jdk的bitset類分別實現(xiàn)bitmap, 方便比較理解：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
package swordoffer;//去除重復并排序import java.util.arrays;import java.util.bitset;import java.util.random;/** * @author gavenyeah * @date time: * @des: */public class bitmap { int arrnum = 800; int len_int = 32; int mmax = 9999; int mmin = 1000; int n = mmax - mmin + 1; public static void main(string args[]) { new bitmap().findduplicate(); new bitmap().finddup_jdk(); } public void finddup_jdk() { system.out.println("*******調用jdk中的庫方法--開始********"); bitset bitarray = new bitset(n); int[] array = getarray(arrnum); for (int i = 0; i < arrnum; i++) { bitarray.set(array[i] - mmin); } int count = 0; for (int j = 0; j < bitarray.length(); j++) { if (bitarray.get(j)) { system.out.print(j + mmin + " "); count++; } } system.out.println(); system.out.println("排序后的數(shù)組大小為：" + count ); system.out.println("*******調用jdk中的庫方法--結束********"); } public void findduplicate() { int[] array = getarray(arrnum); int[] bitarray = setbit(array); printbitarray(bitarray); } public void printbitarray(int[] bitarray) { int count = 0; for (int i = 0; i < n; i++) { if (getbit(bitarray, i) != 0) { count++; system.out.print(i + mmin + "\t"); } } system.out.println(); system.out.println("去重排序后的數(shù)組大小為：" + count); } public int getbit(int[] bitarray, int k) {// 1右移 k % 32位 與上 數(shù)組下標為 k/32 位置的值 return bitarray[k / len_int] & (1 << (k % len_int)); } public int[] setbit(int[] array) {// 首先取得數(shù)組位置下標 i/32, 然后 或上 // 在該位置int類型數(shù)值的bit位：i % 32 int m = array.length; int bit_arr_len = n / len_int + 1; int[] bitarray = new int[bit_arr_len]; for (int i = 0; i < m; i++) { int num = array[i] - mmin; bitarray[num / len_int] |= (1 << (num % len_int)); } return bitarray; } public int[] getarray(int arrnum) { @suppresswarnings("unused") int array1[] = { 1000, 1002, 1032, 1033, 6543, 9999, 1033, 1000 }; int array[] = new int[arrnum]; system.out.println("數(shù)組大小：" + arrnum); random r = new random(); for (int i = 0; i < arrnum; i++) { array[i] = r.nextint(n) + mmin; } system.out.println(arrays.tostring(array)); return array; }} |
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對服務器之家的支持。如果你想了解更多相關內容請查看下面相關鏈接
原文鏈接：https://blog.csdn.net/y999666/article/details/51220833
