在做题中学习(35):判断字符是否唯一

2023-12-21 12:53:03

面试题 01.01. 判定字符是否唯一 - 力扣(LeetCode)

思路:1.用哈希表(创建另一个数组存储)然后和原数组一一比对。

时间复杂度O(N) 空间复杂度 O(N)

2.位图(更优)把26个字母的信息存进一个整型的位中,0表示没出现过,1表示出现过

把用许多整型存储一个信息,改为用一个整型存储多个信息。

时间复杂度O (N)? ? ?空间复杂度O (1)

优化:(鸽巢原理)

?一共有26个英文字母,所给字符串如果>26直接返回false.

class Solution 
{
public:
    bool isUnique(string astr) 
    {
        if(astr.size()>26)
        {
            return false;
        }
        int bitMap = 0;
        for(auto ch:astr)
        {
            int i = ch - 'a';
            //判断有无在位图中出现过(==1?)
            if(((bitMap>>i)&1)==1)
            {
                return false;
            }
            //没有在位图中出现过,放进去(改1)。
            bitMap|=(1<<i);

        }
        return true;
    }
};

文章来源:https://blog.csdn.net/yiren_liusong/article/details/135127422
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。