高級(jí)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用之使用bitmap進(jìn)行字符串去重的方法實(shí)例
bitmap 即為由單個(gè)元素為 boolean（0/1, 0 表示未出現(xiàn)，1 表示已經(jīng)出現(xiàn)過）的數(shù)組。
如果C/C++ 沒有原生的 boolean 類型，可以用 int 或 char 來作為 bitmap 使用，如果我們要判斷某字符（char）是否出現(xiàn)過
使用 int 作為 bitmap 的底層數(shù)據(jù)結(jié)構(gòu)，bitmap 即為 int 數(shù)組，一個(gè) int 長(zhǎng)度為 32 個(gè) bit 位，
- c / 32 ⇒ bitmap 中的第幾個(gè) int
- c % 32 ⇒ bitmap 中的某 int 中的第幾個(gè) bit 位；
使用 char 作為 bitmap 的底層數(shù)據(jù)結(jié)構(gòu)，bitmap 即為 char 數(shù)組，一個(gè) char 長(zhǎng)度為 8 個(gè) bit 位；
- c / 8 ⇒ bitmap 中的第幾個(gè) char
- c % 8 ⇒ bitmap 中某 char 中的第幾個(gè) bit 位；
ASCII
- A-Z：65-90
- a-z：97-122
如果使用 char 作為 bitmap 的替代底層數(shù)據(jù)結(jié)構(gòu)，為了實(shí)現(xiàn)字符串的去重需要 char 的長(zhǎng)度為多少呢？122/8+1 ⇒ 16。如果使用 int 作為 bitmap 的底層實(shí)現(xiàn)，則需要 int 數(shù)組的長(zhǎng)度為 122/32 + 1 ⇒ 4
1. int 作為底層數(shù)據(jù)結(jié)構(gòu)
void dedup(const char* src, char* dst)
{
unsigned int exists[4] = { 0 };
int i = 0, j = 0;
unsigned int mask;
char c;
while (src[i])
{
c = src[i];
mask = 1 << (c % 32);
if ((exists[c / 32] & mask) == 0)
{
dst[j++] = c;
exists[c / 32] |= mask;
}
i++;
}
dst[j] = '\0';
}
2. 使用 char 作為底層數(shù)據(jù)結(jié)構(gòu)
void dedup(const char* src, char* dst)
{
unsigned char exists[16] = { 0 };
int i = 0, j = 0;
unsigned int mask;
char c;
while (src[i])
{
c = src[i];
mask = 1 << (c % 8);
if ((exists[c / 8] & mask) == 0)
{
dst[j++] = c;
exists[c / 8] |= mask;
}
i++;
}
dst[j] = '\0';
}
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接
- JavaScript"模擬事件"的注意要點(diǎn)詳解
- Android Java調(diào)用自己C++類庫的實(shí)例講解
- PyQt5內(nèi)嵌瀏覽器注入JavaScript腳本實(shí)現(xiàn)自動(dòng)化操作的代碼實(shí)例
- 推薦15個(gè)最好用的JavaScript代碼壓縮工具
- JavaScript中.min.js和.js文件的區(qū)別講解
- 實(shí)例講解Java中random.nextInt()與Math.random()的基礎(chǔ)用法
- 談?wù)凧avaScript中super(props)的重要性
- JavaScript常用工具方法封裝
- Java多線程實(shí)戰(zhàn)之交叉打印的兩種方法
- 海量數(shù)據(jù)去重排序bitmap(位圖法)在java中實(shí)現(xiàn)的兩種方法
相關(guān)文章
SpringMVC異常處理知識(shí)點(diǎn)總結(jié)
在本篇文章里小編給大家整理的是關(guān)于SpringMVC異常處理相關(guān)知識(shí)點(diǎn)內(nèi)容，需要的朋友們學(xué)習(xí)下。2019-10-10
List集合對(duì)象中按照不同屬性大小排序的實(shí)例
下面小編就為大家?guī)硪黄狶ist集合對(duì)象中按照不同屬性大小排序的實(shí)例。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-03-03
解決IDEA中Maven項(xiàng)目中JSTL標(biāo)簽無效問題
這篇文章主要介紹了關(guān)于IDEA中Maven項(xiàng)目中JSTL標(biāo)簽無效問題的解決方法,需要的朋友可以參考下2018-09-09
這篇文章主要介紹了Java排序算法總結(jié)之選擇排序,較為詳細(xì)的分析了選擇排序的原理與java實(shí)現(xiàn)技巧,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了JavaPoet的使用指南小結(jié)，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-10-10
Java通過PowerMockito和Mokito進(jìn)行單元測(cè)試的實(shí)現(xiàn)
PowerMockito和Mockito都是Java語言中的測(cè)試框架,用于進(jìn)行單元測(cè)試和集成測(cè)試,本文就來詳細(xì)的介紹一下通過PowerMockito和Mokito進(jìn)行單元測(cè)試,感興趣的可以了解一下2023-08-08
java字符串?dāng)?shù)組進(jìn)行大小排序的簡(jiǎn)單實(shí)現(xiàn)
下面小編就為大家?guī)硪黄猨ava字符串?dāng)?shù)組進(jìn)行大小排序的簡(jiǎn)單實(shí)現(xiàn)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-09-09
Spring中的ApplicationRunner接口的使用詳解
這篇文章主要介紹了Spring中的ApplicationRunner接口的使用詳解,ApplicationRunner使用起來很簡(jiǎn)單,只需要實(shí)現(xiàn)CommandLineRunner或者ApplicationRunner接口,重寫run方法就行,需要的朋友可以參考下2023-11-11
Java?輸入輸出?IO?NIO?AIO三兄弟對(duì)比分析對(duì)比分析
這篇文章主要為大家介紹了Java?輸入輸出?IO?NIO?AIO三兄弟對(duì)比分析對(duì)比分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-04-04
java?kafka如何動(dòng)態(tài)設(shè)置用戶讀寫權(quán)限
這篇文章主要介紹了java?kafka如何動(dòng)態(tài)設(shè)置用戶讀寫權(quán)限問題,具有很好的參考家價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08