CTCI 系列 --1.1 判断一个字符串中的字符是否唯一（C 语言）

原题：

Implement an algorithm to determine if a string has all unique characters.What if you cannot use additional data structures?

实现一个算法，判断一个字符串中的字符是否是唯一的。不能够使用额外的数据结构。

首先得确定构成字符串的字符集有多大？是 ASCII 字符，还是只是 26 个字母？根据不同情况，我们的解决方案可能不同。

下面我们以 ASCII 字符为例，ASCII 码字符可以使用一个字节来表示，有效取值范围为 0~127，总共 128 个字符。
解题思路为，定义一个 128 字节大小 char 型数组，数组初始化为 0,。遍历字符串中的字符，当我们定义的数组中该字符对应位置为 1 则代表该字符在字符串中已出现过，即该字符串中的字符不是唯一的；否则将数据中该字符对应位置置 1。完整遍历一遍字符串，知道到达字符串末尾('\0')。

int check_uniq(char *str)
{
    char flag[128];
    int ret = 0;
    memset(flag, 0, sizeof(flag));
    while (*str++!= '\0')
    {
        if (flag[*str])
        {
            ret = 1; //有重复
            break;
        }
        else
        {
            flag[*str] = 1;
        }
    }
    return ret;
}
​

该算法时间复杂度为 O(n)。算法中标志数组使用了 128Byte，我们还可以进一步减少空间占用到原来的 1/8。即每个 ASCII 码字符的出现状况使用一个 bit 位来指示。算法如下：

int check_uniq2(char *str)
{
    int flag[4];
    int ret = 0;
    memset(flag, 0, sizeof(flag));
    while (*str++ != '\0')
    {
        if (flag[*str/32] & 1<<(*str%32))
        {
            ret = 1; //有重复
            break;
        }
        else
        {
            flag[*str / 32] |= 1 << (*str % 32);
        }
    }
    return ret;
}
​

测试代码如下：

int main(void)
{
    char buf[100];
    while (1)
    {
        memset(buf, 0, sizeof(buf));
        printf("please input string:");
        scanf("%s", buf);
        if (check_uniq2(buf))
        {
            printf("not uniq !\n");
        }
        else
        {
            printf("is uniq !\n");
        }
    }
    return 0;
}
​

运行结果：