目录

剑指Offer之第一个只出现一次的字符

Gsscsd 收录于剑指Offer

2019-04-10 约 283 字预计阅读 1 分钟次阅读

目录

题目描述：

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

解题思路一：

时间复杂度: $O(n)$, 空间复杂度: $O(n)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        map<char, int> map;
        
        for(int i = 0; i < str.length(); i++)
        {
            if(!map[str[i]]) map[str[i]] = 1;
            else map[str[i]]++;
        }
        
         for(int i = 0; i < str.length(); i++)
         {
             if(map[str[i]] == 1) return i;
         }
        
        return -1;
    }
};

解题思路二：

find()的应用（rfind() 类似，只是从反向查找）

找到 – 返回第一个字符的索引

没找到–返回 string::npos

时间复杂度: $O(n)$, 空间复杂度: $O(1)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
public:
    int FirstNotRepeatingChar(string str) {
    
         for(size_t i = 0; i < str.length(); i++)
         {
             if(str.find(str[i]) == str.rfind(str[i])) 
                 return i;
         }
        
        return -1;
    }
};