387. 字符串中的第一个唯一字符

飞询

发布于 2025-08-01 16:48:50

7200

代码可运行

文章被收录于专栏：云同步云同步

运行总次数：0

代码可运行

链接：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

思路

字符串只包含小写字母，也就是只有 26 种字符，那么就可以通过一个 26的 byte 数组来表示哪些是重复的，没出现过，未重复过的，在使用一个 List 来存储第一次出现字符的索引，如果字符前面已经出现过的，就不存进去，这个 list 数组最多也就是存进去26个索引

那么答案就只是从 List 中遍历，判断每个索引对应的字符是否重复过，如果都重复过，那么结果就是 -1，发现有一个是未重复的，那么结果就是这个索引

代码

/**
 * 387. 字符串中的第一个唯一字符
 * 执行用时分布 5 ms 击败 89.86% 消耗内存分布 44.38 MB 击败 49.25%
 * @param s 字符串
 * @return 字符串中的第一个唯一字符
 */
public int firstUniqChar(String s) {
    // 用来表示 26 个字母中的重复情况
    // 0: 代表没有出现过，1：代表出现过，2：代表出现过多次
    byte[] chars = new byte[26];
    // 用于存储出现过一次的字符的下标
    List<Integer> list = new ArrayList<>();
    // 将字符串转换成字符数组，方便遍历
    char[] charArray = s.toCharArray();
    for (int i = 0; i < charArray.length; i++) {
        // 获取这个字符在 26个字符中的位置
        byte index = (byte)(charArray[i] - 'a');
        // 获取这个字符出现的次数
        byte num = chars[index];
        if (num == 0){
            // 将下标添加进 list 中
            list.add(i);
            chars[index] = 1;
        } else if (num == 1){
            // 代表出现多次
            chars[index] = 2;
        }
    }
    // 遍历 list，过滤出后面出现重复的字符
    for (Integer i : list) {
        // 获取这个字符在 26个字符中的位置
        byte index = (byte)(charArray[i] - 'a');
        // 获取这个字符出现的次数
        byte num = chars[index];
        if (num == 1){
            return i;
        }
    }
    return -1;
}

优化

我尝试了几次都没法将运行时间缩减至 4ms，最后将 list 替换成普通的 int 数组，ArrayList 底层如果空间不足会进行扩容，换成普通的 int 数组，缩减掉了这些过程

public int firstUniqChar(String s) {
    // 用来表示 26 个字母中的重复情况
    // 0: 代表没有出现过，1：代表出现过，2：代表出现过多次
    byte[] chars = new byte[26];
    // 用于存储出现过一次的字符的下标
    int[] first = new int[26];
    int firstIndex = 0;
    // 将字符串转换成字符数组，方便遍历
    char[] charArray = s.toCharArray();
    for (int i = 0; i < charArray.length; i++) {
        // 获取这个字符在 26个字符中的位置
        byte index = (byte)(charArray[i] - 'a');
        // 获取这个字符出现的次数
        byte num = chars[index];
        if (num == 0){
            // 将下标添加进 list 中
            first[firstIndex++] = i;
            chars[index] = 1;
        } else if (num == 1){
            // 代表出现多次
            chars[index] = 2;
        }
    }
    // 遍历 first，过滤出后面出现重复的字符
    for (Integer i : first) {
        // 获取这个字符在 26个字符中的位置
        byte index = (byte)(charArray[i] - 'a');
        // 获取这个字符出现的次数
        byte num = chars[index];
        if (num == 1){
            return i;
        }
    }
    return -1;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-01，如有侵权请联系 cloudcommunity@tencent.com 删除

索引