描述

题目描述

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

示例

输入："google"
返回值：4

知识点：字符串，哈希表，数组
难度：一星

题解

解题思路

第一个一般都会想到采用哈希表来保存字符出现的次数、是否只出现一次。

还可以利用其他数据类型的特性，如队列的先进先出，数组的有序性。

方法一：hash存放布尔值

图解

image-20210622172119579

算法流程：
  • 哈希表存储布尔值，表示是否只出现一次
  • 使用一个Map，只需存储52个大小写字母
  • 重复出现的字符，对应value为false，只出现一次的字符value为true
  • 遍历字符串数组，找到第一个value为true的字符
Java 版本代码如下：
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int FirstNotRepeatingChar(String s) {
        // 只需存储52个大小写字母
        Map<Character, Boolean> dic = new HashMap<>(52); 
        char[] sc = s.toCharArray();
        // 重复出现的字符，对应value为false，只出现一次的字符value为true
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        // 找到第一个value为true的字符
        int cnt = 0;
        for(char c : sc){
            if(dic.get(c)){
                return cnt;
            }
            ++cnt;
        }
        return -1;
    }
}

复杂度分析：

时间复杂度：O(N) ，需遍历 s 两次字符串长度N
空间复杂度：O(1)，Map只需要52的空间大小，因此只要常数级空间复杂度

方法二：hash存放字符出现次数

算法流程：
  • new 一个 map：key字符, value为出现次数
  • 第一次出现的字符存储value为 1
  • 统计每个字符串出现次数
  • 遍历字符数字，找到第一个字符出现次数为1的字符并返回索引
Java 版本代码如下：

哈希表存储字符出现次数

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        // key字符, value为出现次数
        Map<Character, Boolean> map = new HashMap<>(52);
        for(int i = 0; i < str.length(); i++) {
            // 第一次出现的字符存储value为 1
            map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) + 1);
        }
        for(int i = 0; i < str.length(); i++) {
            if(map.get(str.charAt(i)) == 1) {
                // 直接返回索引
                return i;
            }
        }
        return -1;
    }
}
Python 版本代码如下：
# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if not s:
            return -1
        # 遍历，找到出现次数为1的字符
        for i in range(len(s)):
            if s.count(s[i]) == 1:
                return i
        return -1

复杂度分析：

时间复杂度：O(N) ，需遍历 s 两次字符串长度N
空间复杂度：O(1)，Map只需要52的空间大小，因此只要常数级空间复杂度

总结：学会Map的存储类型的灵活使用

方法三：数组

说到底数组的用法和上面的 Map 差不多，也是存储字母出现次数，只不过需要以字母的ASCII码为下标存储，节省了类似Map存储字符的空间

算法流程：
  • new一个数组，数组以每个字母的ASCII码为下标, 存放对应字符出现次数
  • 统计每个字符出现次数
  • 找到数组中为 1 的对应下标
Java 版本代码如下：
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        // 数组存储字符出现次数
        int[] words = new int[58];
        // 统计每个字符出现次数
        for(int i = 0;i < str.length();i++){
            // 数组以每个字母的ASCII码为下标, 存放对应字符出现次数
            words[((int)str.charAt(i))-65] += 1;
        }
        for(int i = 0; i < str.length(); i++){
            if(words[((int)str.charAt(i))-65]==1)
                return i;
        }
        return -1;
    }
}
Python 版本代码如下：
# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # 数组统计出现次数
        single_list = []
        for i in range(len(s)):
            if s.count(s[i]) == 1:
                return i
                # 字符存放到数组，用于计数
                single_list.append(s[i])
                break
        if len(single_list) == 0:
            return -1
        # write code here

复杂度分析：

时间复杂度：O(N) ，需遍历 s 两次字符串长度N
空间复杂度：O(1)，数组只需要常数级的空间大小，因此只要常数级空间复杂度

总结：对于这种统计次数的往往能运用到其他数据类型