讨论/《初级算法》 - 字符串中的第一个唯一字符/
《初级算法》 - 字符串中的第一个唯一字符
共 57 个回复

JavaScript 解法
只要第一个和最后一个的索引一致,那肯定是只有这个是对的了

var firstUniqChar = function(s) {
    for(let i=0;i<s.length;i++){
        if(s.lastIndexOf(s[i])===s.indexOf(s[i])){
             return i
        }
    }
    return -1
};
36

1,两次遍历

第一遍先统计每个字符出现的次数,第二遍再次从前往后遍历字符串s中的每个字符,如果某个字符出现一次直接返回,原来比较简单,看下代码

    public int firstUniqChar(String s) {
        int count[] = new int[26];
        char[] chars = s.toCharArray();
        //先统计每个字符出现的次数
        for (int i = 0; i < s.length(); i++)
            count[chars[i] - 'a']++;
        //然后在遍历字符串s中的字符,如果出现次数是1就直接返回
        for (int i = 0; i < s.length(); i++)
            if (count[chars[i] - 'a'] == 1)
                return i;
        return -1;
    }


2,使用HashMap解决

也是换汤不换药,原来和上面的一样,先统计每个字符的数量,然后在查找

    public int firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap();
        char[] chars = s.toCharArray();
        //先统计每个字符的数量
        for (char ch : chars) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        //然后在遍历字符串s中的字符,如果出现次数是1就直接返回
        for (int i = 0; i < s.length(); i++) {
            if (map.get(chars[i]) == 1) {
                return i;
            }
        }
        return -1;
    }


3,使用Java的api

一个从前查找,一个从后查找,如果下标相等,说明只出现了一次

    public int firstUniqChar(String s) {
        for (int i = 0; i < s.length(); i++)
            if (s.indexOf(s.charAt(i)) == s.lastIndexOf(s.charAt(i)))
                return i;
        return -1;
    }


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

14

自制哈希表效率更高(用两个数组实现)

class Solution {
public:
    int firstUniqChar(string s) {
        int a[26]={0};
        int index[26];
        int size=s.size();
        for(int i=0;i<size;i++)
        {
            a[s[i]-'a']++;
            index[s[i]-'a']=i;
        }
        for(int i=0;i<size;i++)
        {
            if(a[s[i]-'a']==1)
            {
                return index[s[i]-'a'];
            }
        }
        return -1;
    }
};

image.png

13

方法3: 使用 find 和 rfind

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for x in s:
            if s.find(x) == s.rfind(x):
                return s.find(x)
        return -1 
7

解法虽然巧妙,但如果考虑indexOf的时间复杂度,哈希表更优

3

python 3
循环遍历方法,此方法时间太长不建议

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for i in range(len(s)):
            if s.count(s[i]) == 1:
                return s.index(s[i])
        return -1

使用字典

class Solution:
    def firstUniqChar(self, s: str) -> int:
        s_dict = {}
        for x in s:
            if x not in s_dict:
                s_dict.update({x: s.count(x)})
        for y in s_dict.keys():
            if s_dict[y] == 1:
                return s.index(y)
        return -1
2

class Solution {
public:
int firstUniqChar(string s)
{
for(int i=0;i<s.size();i++)
{
if(s.find(s[i])==s.rfind(s[i]))
return i;
}
return -1;
}
};

2

使用HashMap存储

class Solution {
    public int firstUniqChar(String s) {
        int length = s.length();
        // 使用HashMap存储字符串
        HashMap<String,Integer> map = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            String c = s.substring(i,i+1);
            if(map.containsKey(c)){
                map.put(c,map.get(c) + 1);
            }else {
                map.put(c,1);
            }
        }
        // 遍历字符串,HashMap中 value 为1的即为单独值,直接返回
        for (int i = 0; i < length; i++) {
            String c = s.substring(i,i+1);
            if(map.get(c) ==1){
                return i;
            }
        }
        return -1;
    }
}
2

Python3
使用python3很简单,使用标准库collections函数Counter,HashMap方法速度又快写起来又简单,Python YYDS!

class Solution:
    def firstUniqChar(self, s: str) -> int:
        temp = collections.Counter(s)
        for i in range(len(s)):
            if temp[s[i]] == 1:
                return i
        return -1
1
/*
int firstUniqChar(char * s){
	//返回只有唯一一个的字符索引
	int i = 0;//标记出现
	int j = 0;
	int k = 0;//标记重复出现
	while (s[j] != 0)
	{
		int  w=i;
		if ((w >> (s[j] - 'a'))&1)
		{
			k |=1 << (s[j++] - 'a');
			continue;
		}
		i |= 1 << (s[j++] - 'a');
	}
	i -=k;
	j = 0;
	while (s[j] != 0)
	{
		if (1 << (s[j++] - 'a') == i)
		{
			break;
		}
	}
	return i ? --j : -1;
}*/
int firstUniqChar(char* s) {
	int i = 0;
	int j = 0;
	while (s[j] != 0)
	{
		bool flag = false;//重复判断标准
		int  w = i;
		if ((w >> (s[j] - 'a')) & 1)//前面重复找下一个
		{
			j++;
			continue;
		}
		for (int m = j + 1; s[m] != 0; m++) {//前面不重复,判断后面重复
			if (s[j] == s[m]) {
				flag = true;//重复修改标记
				break;
			}
		}//退出循环的条件为没找见重复或找见
		if (flag) {
			i |= 1 << (s[j++] - 'a');
		}
		else {
			return j;
		}

	}
	return -1;
}
1