高級(jí)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用之使用bitmap進(jìn)行字符串去重的方法實(shí)例

更新時(shí)間：2019年02月18日 09:00:40 作者：Inside_Zhang

今天小編就為大家分享一篇關(guān)于高級(jí)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用之使用bitmap進(jìn)行字符串去重的方法實(shí)例，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧

bitmap 即為由單個(gè)元素為 boolean（0/1, 0 表示未出現(xiàn)，1 表示已經(jīng)出現(xiàn)過）的數(shù)組。

如果C/C++ 沒有原生的 boolean 類型，可以用 int 或 char 來(lái)作為 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)鏈接

您可能感興趣的文章:

相關(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ī)?lái)一篇List集合對(duì)象中按照不同屬性大小排序的實(shí)例。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧
2017-03-03
解決IDEA中Maven項(xiàng)目中JSTL標(biāo)簽無(wú)效問題
這篇文章主要介紹了關(guān)于IDEA中Maven項(xiàng)目中JSTL標(biāo)簽無(wú)效問題的解決方法,需要的朋友可以參考下
2018-09-09
Java排序算法總結(jié)之選擇排序
這篇文章主要介紹了Java排序算法總結(jié)之選擇排序,較為詳細(xì)的分析了選擇排序的原理與java實(shí)現(xiàn)技巧,需要的朋友可以參考下
2015-05-05
JavaPoet的使用指南小結(jié)
這篇文章主要介紹了JavaPoet的使用指南小結(jié)，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧
2018-10-10
Java通過PowerMockito和Mokito進(jìn)行單元測(cè)試的實(shí)現(xiàn)
PowerMockito和Mockito都是Java語(yǔ)言中的測(cè)試框架,用于進(jìn)行單元測(cè)試和集成測(cè)試,本文就來(lái)詳細(xì)的介紹一下通過PowerMockito和Mokito進(jìn)行單元測(cè)試,感興趣的可以了解一下
2023-08-08
java字符串?dāng)?shù)組進(jìn)行大小排序的簡(jiǎn)單實(shí)現(xiàn)
下面小編就為大家?guī)?lái)一篇java字符串?dāng)?shù)組進(jìn)行大小排序的簡(jiǎn)單實(shí)現(xiàn)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧
2016-09-09
Spring中的ApplicationRunner接口的使用詳解
這篇文章主要介紹了Spring中的ApplicationRunner接口的使用詳解,ApplicationRunner使用起來(lái)很簡(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