java如何使用bitmap進行字符串去重

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

bitmap 即為由單個元素為 boolean（0/1, 0 表示未出現，1 表示已經出現過）的數組。

如果C/C++ 沒有原生的 boolean 類型，可以用 int 或 char 來作為 bitmap 使用，如果我們要判斷某字符（char）是否出現過

使用 int 作為 bitmap 的底層數據結構，bitmap 即為 int 數組，一個 int 長度為 32 個 bit 位，

• c / 32 ? bitmap 中的第幾個 int

• c % 32 ? bitmap 中的某 int 中的第幾個 bit 位；

使用 char 作為 bitmap 的底層數據結構，bitmap 即為 char 數組，一個 char 長度為 8 個 bit 位；

• c / 8 ? bitmap 中的第幾個 char

• c % 8 ? bitmap 中某 char 中的第幾個 bit 位；

ASCII

• A-Z：65-90

• a-z：97-122

如果使用 char 作為 bitmap 的替代底層數據結構，為了實現字符串的去重需要 char 的長度為多少呢？122/8+1 ? 16。如果使用 int 作為 bitmap 的底層實現，則需要 int 數組的長度為 122/32 + 1 ? 4

1. int 作為底層數據結構

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 作為底層數據結構

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進行字符串去重”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！