专栏首页EdisonTalk剑指Offer面试题:30.第一个只出现一次的字符

剑指Offer面试题:30.第一个只出现一次的字符

一、题目:第一个只出现一次的字符

题目:在字符串中找出第一个只出现一次的字符。如输入"abaccdeff",则输出'b'。要求时间复杂度为O(n)

  最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较,如果在后面没有发现重复的字符,则该字符就是只出现一次的字符。如果字符串有n个字符,每个字符可能与后面的O(n)个字符相比较,因此这种思路的时间复杂度是O(n2),但是不满足要求。

二、解题思路:以空间换时间

   为了解决这个问题,我们可以定义一个哈希表(外部空间),其键值(Key)是字符,而值(Value)是该字符出现的次数。

  同时我们还需要从头开始扫描字符串两次:

  (1)第一次扫描字符串时,每扫描到一个字符就在哈希表的对应项中把次数加1。(时间效率O(n))

  (2)第二次扫描时,每扫描到一个字符就能从哈希表中得到该字符出现的次数。这样第一个只出现一次的字符就是符合要求的输出。(时间效率O(n))

  这样算起来,总的时间复杂度仍然是O(n),满足了题目要求,擦一擦汗,感叹:这*装得真有点技术!

  装完了B,开始将这个想法实现为代码:

    public static char FirstNotRepeatingChar(string str)
    {
        if(string.IsNullOrEmpty(str))
        {
            return '\0';
        }

        char[] array = str.ToCharArray();
        const int size = 256;
        // 借助数组来模拟哈希表,只用1K的空间消耗
        uint[] hastTable = new uint[size];
        // 初始化数组
        for (int i = 0; i < size; i++)
        {
            hastTable[i] = 0;
        }

        for (int i = 0; i < array.Length; i++)
        {
            hastTable[array[i]]++;
        }

        for (int i = 0; i < array.Length; i++)
        {
            if (hastTable[array[i]] == 1)
            {
                return array[i];
            }
        }

        return '\0';
    }

PS:字符(char)是一个长度为8的数据类型,因此总共有256种可能。(在C#中char则是长度为16位也就是2个字节)这里我们只列举char是1个字节的情况,我们创建一个长度为256的数组来模拟哈希表,每个字母根据其ASCII码值作为数组的下标对应数组的一个数字,而数组中存储的是每个字符出现的次数。计算下来,它的大小是256*4字节(1个int类型在Windows下占4个字节)=1K。由于这个数组的大小是个常数,因此可以认为这种算法的空间复杂度是O(1)。 

三、单元测试

3.1 测试用例

    // 常规输入测试,存在只出现一次的字符
    [TestMethod]
    public void FirstCharTest1()
    {
        char actual = CharHelper.FirstNotRepeatingChar("google");
        Assert.AreEqual(actual, 'l');
    }

    // 常规输入测试,不存在只出现一次的字符
    [TestMethod]
    public void FirstCharTest2()
    {
        char actual = CharHelper.FirstNotRepeatingChar("aabccdbd");
        Assert.AreEqual(actual, '\0');
    }

    // 常规输入测试,所有字符都只出现一次
    [TestMethod]
    public void FirstCharTest3()
    {
        char actual = CharHelper.FirstNotRepeatingChar("abcdefg");
        Assert.AreEqual(actual, 'a');
    }

    // 鲁棒性测试,输入NULL
    [TestMethod]
    public void FirstCharTest4()
    {
        char actual = CharHelper.FirstNotRepeatingChar(null);
        Assert.AreEqual(actual, '\0');
    }

3.2 测试结果

  (1)测试通过情况

  (2)代码覆盖率

四、总结扩展

  如果需要判断多个字符是不是在某个字符串里出现过或者统计多个字符在某个字符串中出现的次数,我们都可以考虑基于数组创建一个简单的哈希表(或者使用基类库中提供的现成的哈希表结构类型)。这样可以用很小的空间消耗换来换取时间效率的提升。

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer面试题:2.二维数组中的查找

      例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。

    Edison Zhou
  • .NET Core微服务之基于Ocelot+IdentityServer实现统一验证与授权

      这里,假设我们有两个客户端(一个Web网站,一个移动App),他们要使用系统,需要通过API网关(这里API网关始终作为客户端的统一入口)先向Identit...

    Edison Zhou
  • 走向面试之数据库基础:二、SQL进阶之case、子查询、分页、join与视图

      假设我们有一个论坛网站,其中有一张User表{ UId,Name,Level },Level是一个int类型,代表了用户等级类型,例如:1代表骨灰,2代表大...

    Edison Zhou
  • 【剑指offer】字符流中第一个不重复的字符

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【LeetCode08】字符串转换整数

    1 )删除掉字符串的空格,这里用到了lstrip()方法,截掉字符串左边的空格或指定字符

    Sam Gor
  • 第一个只出现一次的字符

    题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 看到这道题时,最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某...

    猿人谷
  • Java中判断字符是否为字母或数字

    Character.isDigit(char c) 判断字符c是否是数字字符,如‘1’,‘2’,是则返回true,否则返回false

    乐心湖
  • grep命令及正则表达式

    grep基本概念 grep:global search regular expression and print out the line. 作用:文本过滤器,...

    小小科
  • Java IO学习笔记总结

    爱撒谎的男孩
  • linux之grep命令

    输出文件中包含'Kell'的文件。.为任意字符,所以合计5个字符,其中第五个字符为任意字符。

    Y大宽

扫码关注云+社区

领取腾讯云代金券