java如何使用bitmap進(jìn)行字符串去重

這篇文章主要介紹java如何使用bitmap進(jìn)行字符串去重，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

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

如果C/C++ 沒(méi)有原生的 boolean 類(lèi)型，可以用 int 或 char 來(lái)作為 bitmap 使用，如果我們要判斷某字符（char）是否出現(xiàn)過(guò)

使用 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';
}

以上是“java如何使用bitmap進(jìn)行字符串去重”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！