首页 > 试题广场 > 第一个只出现一次的字符
[编程题]第一个只出现一次的字符
  • 热度指数:348912 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).

说一下解题思路哈,其实主要还是hash,利用每个字母的ASCII码作hash来作为数组的index。首先用一个58长度的数组来存储每个字母出现的次数,为什么是58呢,主要是由于A-Z对应的ASCII码为65-90,a-z对应的ASCII码值为97-122,而每个字母的index=int(word)-65,比如g=103-65=38,而数组中具体记录的内容是该字母出现的次数,最终遍历一遍字符串,找出第一个数组内容为1的字母就可以了,时间复杂度为O(n)

public static int solution(String str){
    int[] words = new int[58];
    for(int i = 0;i<str.length();i++){
        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;
}
编辑于 2017-07-20 08:56:32 回复(18)
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        map<char, int> mp;
        for(int i = 0; i < str.size(); ++i)
            mp[str[i]]++;
        for(int i = 0; i < str.size(); ++i){
            if(mp[str[i]]==1)
                return i;
        }
        return -1;
    }
};

发表于 2017-06-05 14:06:18 回复(46)
import java.util.LinkedHashMap;
// use linkedhashmap to keep the order
public class Solution {
    public int FirstNotRepeatingChar(String str) {
		LinkedHashMap <Character, Integer> map = new LinkedHashMap<Character, Integer>();
		for(int i=0;i<str.length();i++){
			if(map.containsKey(str.charAt(i))){
				int time = map.get(str.charAt(i));
				map.put(str.charAt(i), ++time);
			}
			else {
				map.put(str.charAt(i), 1);
			}
		}
    	int pos = -1;  	
    	int i=0;
    	for(;i<str.length();i++){
    		char c = str.charAt(i);
    		if (map.get(c) == 1) {
				return i;
			} 
    	}
    	return pos;
	}
}

发表于 2015-07-28 20:12:05 回复(59)
import java.util.HashMap;
public class Solution {
   HashMap<Character, Integer> map = new HashMap<>();

    public int FirstNotRepeatingChar(String str) {
        if (str==null)return -1;
        int length = str.length();
        for(int i = 0;i<length;i++) {
            
            if(map.containsKey(str.charAt(i))){
                int value = map.get(str.charAt(i));
                map.remove(str.charAt(i));
                map.put(str.charAt(i),value+1);
            }else{
                map.put(str.charAt(i),1);
            }
        }
     for(int i = 0;i<length;i++){
         if(map.get(str.charAt(i))==1)
             return i;
     	}
        return -1;   
	}
}

发表于 2016-04-16 12:28:45 回复(11)
public int FirstNotRepeatingChar(String str)
	{
		char[] c = str.toCharArray();
		int[] a = new int['z'];
		for (char d : c)
			a[(int) d]++;
		for (int i = 0; i < c.length; i++)
			if (a[(int) c[i]] == 1)
				return i;
		return -1;
	}

发表于 2015-10-20 16:03:41 回复(61)

python一行就够了:


class Solution:
    def FirstNotRepeatingChar(self, s):
        return s.index(list(filter(lambda c:s.count(c)==1,s))[0]) if s else -1
发表于 2017-10-07 16:47:13 回复(30)
标准的书本解法,先在hash表中统计各字母出现次数,第二次扫描直接访问hash表获得次数
    int FirstNotRepeatingChar(string str) {
        if ( str.length() == 0)
            return -1;
        
        unsigned int hashTime[256] = {0};
        for(int i =0;i<str.length();++i)
            hashTime[str[i]]++;
        
        for(int i =0;i<str.length();++i)
        {
            if(hashTime[str[i]] == 1)
                return i;
        }
        return -1;
    }

发表于 2016-06-28 09:07:38 回复(25)
# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        #判断输入条件
        if len(s)<=0 or len(s)>10000:
            return -1
        #count用于统计字符串中某个字符的出现个数
        #index为计算字符串中某个字符的位置
        for i in s:
            if s.count(i)==1:
                return s.index(i)
                break
Python:开始想用字典,但是字典是无序的,所以无法找到第一个出现次数为1的位置
我用的是python内置函数完成的,没有提现到算法思想,
看到书中是建一个哈希表,以字母的ascii为下标,出现次数为值,然后再遍历一次找到第一个值为1的位置,用python编写如下:
    #建立哈希表,字符长度为8的数据类型,共有256种可能,于是创建一个长度为256的列表
        ls=[0]*256
        #遍历字符串,下标为ASCII值,值为次数
        for i in s:
            ls[ord(i)]+=1
        #遍历列表,找到出现次数为1的字符并输出位置
        for j in s:
            if ls[ord(j)]==1:
                return s.index(j)
                break


发表于 2017-10-15 15:12:13 回复(7)
题目各种坑...
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.length()==0)
            return -1;
        int hash[256]={0};
        int i=0;
        while(str[i]!='\0'){
            hash[str[i]]++;
            ++i;
        }
        i=0;
        while(str[i]!='\0'){
            if(1==hash[str[i]]){
                return i;
            }
            i++;
        }
        return -1;
    }
};

发表于 2015-07-27 10:58:12 回复(25)
发表于 2017-07-26 20:17:21 回复(5)
python简单方法:
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if len(s)<0:
            return -1
        for i in s:
            if s.count(i)==1:
                return s.index(i)
                break
        return -1
书中所述创建哈希表,下标为ACII值,值为出现次数
#建立哈希表,字符长度为8的数据类型,共有256种可能,于是创建一个长度为256的列表
        ls=[0]*256
        #遍历字符串,下标为ASCII值,值为次数
        for i in s:
            ls[ord(i)]+=1
        #遍历列表,找到出现次数为1的字符并输出位置
        for j in s:
            if ls[ord(j)]==1:
                return s.index(j)
                break
        return -1

编辑于 2017-10-19 17:01:38 回复(10)

都是字母 肯定在ASCII码范围内
直接用数组哈希

class Solution {
public:
    int ha[256];
    int FirstNotRepeatingChar(string str){
        memset(ha, 0, sizeof(ha));
        for(int i=0;i<str.length();i++) ha[int(str[i])]++;
        for(int i=0;i<str.length();i++) if(ha[int(str[i])] == 1) return i;
        return -1;
    }
};
发表于 2018-12-10 09:27:06 回复(0)
几个坑:
1.题目表述不清楚:到底返回神马东西?字符位置还是字符的ASCII值?
2.测试用例不和题目:题目要求是全部大写字母,给个"google"作为测试是几个意思?
3.返回值没有说明,字符串空串为什么返回是-1?
OL:出题目不带的这样让写代码的乱猜的

补上一个Java AC代码:
public class Solution {
public int FirstNotRepeatingChar(String str) {
        if (str.length() == 0) {
            return  -1;
        }
        char c = 'A';
        if(str.charAt(0) >= 'a'){
            c = 'a';
        }
        int[] counts = new int[26];
        for (int i = 0; i < str.length(); i++) {
            counts[str.charAt(i) - c]++; 
        }
        for (int i = 0; i < str.length(); i++) {
            if (counts[str.charAt(i) - c] == 1){
                return i;
            }
        }
        return -1;
    }
}

编辑于 2016-08-31 10:18:35 回复(18)
    def FirstNotRepeatingChar(self, s):
        if s == "":
            return -1
        else:
            counts = {}
            for i in s:
                if i not in counts:
                    counts[i] = 1
                else:
                    counts[i] += 1
            for index,i in enumerate(s):
                if counts[i] == 1:
                    return index

发表于 2017-07-11 17:56:48 回复(6)
class Solution {
public:
//坑爹啊,说长度在1<=length<=1000的,结果放了个空,返回-1.
//说是大写字母,结果给个google什么意思。还是做了个256的hash表。
    int FirstNotRepeatingChar(string str) {
        unsigned int ch[256]={0};
        if(str.length()<=0) return -1;
        for(int i=0;i<str.length();i++)
        {
                ch[(int)str[i]]++;
        }
        for(int i=0;i<str.length();i++)
        {
            if(ch[(int)str[i]]==1)
                return i;
        }
        return -1;
    }
};

发表于 2016-07-21 09:56:08 回复(1)
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        char[] chars = str.toCharArray();
        int[] map = new int[256];
        for (int i = 0; i < chars.length; i++) {
            map[chars[i]]++;
        }
        for (int i = 0; i < chars.length; i++) {
            if (map[chars[i]] == 1) return i;
        }
        return -1;
    }
}

发表于 2017-07-26 11:08:37 回复(7)
python
#方法一:利用数组自己建立个哈希表
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if s==' ':
            return -1
        hashtable=[0]*256
        for i in s:
            hashtable[ord(i)] += 1
        for i in s:
            if hashtable[ord(i)]==1:
                return s.index(i)
        return -1

#方法二:利用python自带的字典
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if s==' ':
            return -1
        d=dict()
        #第一次遍历字符串,将每个字符的次数存入字典
        for i in s:    
            d[i]=d.get(i,0)+1
        #第二次遍历字符串,检查每个字符出现的次数
        for i in s:
            if d[i]==1:   #O(1)
                return s.index(i)
        return -1

发表于 2019-03-23 21:29:36 回复(0)
import java.util.HashMap;
import java.util.Map;

/**

*
* 方法一 : 用hashmap的性质,因为containsKey是O(1)
*
*
* 方法二: 桶排序,用两个桶保存,一个保存index,一个保存出现次数
*/
public class FirstNotRepeatingChar {

public int firstNotRepeatingChar(String str) {
if (str == null || str.length() == 0 ) {
return -1;
}
        Map<Character, Integer> map = new HashMap<>();
char[] arr = str.toCharArray();
for (int i = 0; i < arr.length; i++) {
if(!map.containsKey(arr[i])) {
map.put(arr[i], i);
} else {
map.put(arr[i], 10001);
}
}
int index =  10001;
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getValue() < index) {
index = entry.getValue();
}
}
return index == 10001 ? -1 : index;
}

//方法二,桶排序,假设只存在大小写字母
public int firstNotRepeatingChar2(String str) {
if (str == null || str.length() == 0 ) {
return -1;
}
int [] arr = new int[200];
int [] arr2 = new int[200];
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
arr[chars[i]] ++;
arr2[chars[i]] = i;
}
int index = 10001;
for (int i = 0; i < arr.length; i++) {
if(arr[i] == 1 && arr2[i] < index) {
index = arr2[i];
}
}
return index == 10001 ? -1 : index;
}
}

编辑于 2018-08-29 18:04:36 回复(1)
//java直接有判断字符是否存在的函数
//我们只要判断在这个字符之前的字符和之后字符是否存在就可以判断字符是否唯一

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        char[] a = str.toCharArray();
        for (int i=0;i<a.length;i++){
            if (!str.substring(0,i).contains(a[i]+"")&&!str.substring(i+1).contains(a[i]+""))
                return i;
        }
        return -1;
    }
}



编辑于 2017-10-13 20:13:35 回复(3)
C++
class Solution {
public:
	int FirstNotRepeatingChar(string str) {
		int size = str.size();
		if (size<1 || size>10000)
			return -1;
		set<char> s1;
		set<char> s2;
		for (int i = 0; i < size; i++)
		{
			if (!s1.insert(str[i]).second)
				s2.insert(str[i]);
		}
		if (s1.empty())
			return -1;
		for (int j = 0; j < size; j++)
		{
			if (s2.insert(str[j]).second)
				return j;
		}
		return -1;
	}
};

发表于 2019-08-07 00:02:18 回复(0)