首页 > 试题广场 >

第一个只出现一次的字符

[编程题]第一个只出现一次的字符

热度指数：565015 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个长为字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

数据范围： $0 \le n \le 10000$ ，且字符串只有字母组成。

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

"google"

输出

示例2

输入

"aa"

输出

-1

算法知识视频讲解

查看答案及解析

金枪葫芦娃

题目各种坑...
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)

Python

人民的名义

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 回复(15)

Python

加油sssssp在招手

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 回复(5)

Python

顧左

    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 回复(9)

Java

瑟瑟不想说话

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)

世界和平123

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 回复(8)

波澜高音哥

Java 28ms 9M 代码呈上:

int[] a = new int[58];

        for(int i=0; i<str.length(); i++) {
            a[str.charAt(i) - 'A'] += 1;
        }
        for(int j=0; j<str.length(); j++) {
            if(a[str.charAt(j) - 'A'] == 1) {
                return j;
            }
        }
return -1;

发表于 2019-03-04 14:48:35 回复(1)

writezen

import java.util.HashMap;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();

        
        for (int i = 0; i < str.length(); i++) {

            if (!hashMap.containsKey(str.charAt(i))) {
                hashMap.put(str.charAt(i), 1);
            } else {
                hashMap.put(str.charAt(i), hashMap.get(str.charAt(i)) + 1);
            }

        }
        
        for (int i = 0; i < str.length(); i++) {
            if(hashMap.get(str.charAt(i))==1){
                return i;
            }
            
        }
        return -1;
    }
}

发表于 2015-05-09 00:06:59 回复(0)

QT菜鸡弟弟

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)

C/C++

全论坛最菜

bitmap法求解，空间最优

一共有256个字符，每个字符用2位来记录它当前出现的次数，00表示没有出现，01表示出现1次，10表示出现两次以上，所以bitmap的大小应该为256*2=512 bit，一个int是四个字节，32bit，所以需要大小为16的int数组就可以存储所有的表示

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int* bitmap = new int[16]();
        int arr_idx, bit_idx;
        for(int i = 0; i < str.length(); ++i){
            arr_idx = str[i] * 2 / 32;
            bit_idx = str[i] * 2 % 32;
            if(((bitmap[arr_idx] >> bit_idx) & 1) == 0){
                bitmap[arr_idx] |= (1 << bit_idx);
            }else if(((bitmap[arr_idx] >> (bit_idx+1)) & 1) == 0){
                bitmap[arr_idx] |= (1 << (bit_idx+1));
            }
        }
        for(int i = 0; i < str.length(); ++i){
            arr_idx = str[i] * 2 / 32;
            bit_idx = str[i] * 2 % 32;
            if(((bitmap[arr_idx] >> bit_idx) & 1) == 1 && ((bitmap[arr_idx] >> (bit_idx+1)) & 1) == 0){
                return i;
            }
        }
        return -1;
    }
};

发表于 2019-04-12 23:40:55 回复(0)

还不快到碗里来

import java.util.ArrayList;
/**
*用ArrayList存储字符数组，每次删除字符数组中一种字符
*若删除后字符数组长度-1，则证明该字符只出现一次
*/
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str.equals(""))
            return -1;
        for(int j = 0;j < str.length();j++){
            ArrayList<Character> list = new ArrayList<Character>();
            for(int i = 0;i < str.length();i++){
		 list.add(str.charAt(i));
	    }
	    for(int i = 0,len = list.size();i < len;i++ ){
		if(list.get(i) == str.charAt(j)){
		list.remove(i);
		 --len;
	         --i;
		}
	     }
	    if(str.length() - list.size() == 1)
		return j;
	}
	return 0;
    }
}

编辑于 2017-07-27 16:49:50 回复(0)

啦啦啦！终于可以改名啦

public class Solution_35 {
    public int FirstNotRepeatingChar(String str) {
    	if(str.equals("")) return -1;
    	int[][] map = new int[58][2];
    	
    	for (int i = 0; i < str.length(); i++) {
			char c = str.charAt(i);
			int pos = c - 'A';
			if(map[pos][0] == 0){
				map[pos][1] = i;
			}
			map[pos][0]++;
		}
    	
    	int ret = Integer.MAX_VALUE;
    	for (int i = 0; i < 58; i++) {
			if(map[i][0] == 1){
				ret = Math.min(ret, map[i][1]);
			}
		}
    	
        return ret;
    }
}

发表于 2017-05-29 18:41:22 回复(0)

沉默的时光

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int len=str.length();//也可以用size()；
        if(len<1||len>10000) return -1;
        int hashmap[256]={0},i;
        for(i=0;i<len;i++){
            hashmap[str[i]]++;
        }
        for(i=0;i<len;i++){
            if(hashmap[str[i]]==1) return i;
        }
        return -1;
    }
};

发表于 2017-03-18 17:33:37 回复(1)

林家花美男

class Solution {

public:

int FirstNotRepeatingChar(string str) {

if(str.empty())

return -1;

int array[256]={0};

for(int i=0;i<str.size();i++)

array[str[i]]++;

int result=-1;

for(int i=0;i<str.size();i++){

if(array[str[i]]==1){

result = i;

break;

}

return result;

}

};

编辑于 2016-08-06 10:47:26 回复(0)

搬一块叫CV的砖

//题目各种坑
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int length = str.size();
        int i=0;
        if(length==0)
            return -1;
        const int tableSize = 26;
        unsigned int hashTable[tableSize];
        
        for(int i=0;i<tableSize;i++)
            hashTable[i]=0;
        i=0;
        while(str[i]!='\0')
        {
            hashTable[str[i++]-'a']++;
        }
        i=0;
        while(str[i]!='\0')
        {
            if(hashTable[str[i++]-'a']==1)
                break;
             
            
            
        }
        if(str[i]=='\0')
            return -1;
        else
            return i-1;
        
    }
};

发表于 2016-03-22 21:21:41 回复(0)

mispsure

//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)

Pis

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

    }
};

发表于 2015-12-27 16:55:39 回复(2)

C++

似水流年ヽ如歌彻婉颜

class Solution {
public:
int FirstNotRepeatingChar(string str) {
const int len = str.length();
int result = -1;
for (int i = 0; i < len; i++) {
char c = str.at(i);
string rightStr = str.substr(i + 1);
if (rightStr.find(c) == -1 && i == str.find_first_of(c)) {
result = i;
break;
}
}
return result;
}
};

发表于 2022-07-05 23:01:18 回复(0)

Python 3

Ron1997

class Solution:
    def FirstNotRepeatingChar(self , str: str) -> int:
        # write code here
        li=[]
        for i in range(len(str)):
            if str[i] not in li:
                li.append(str[i])
            else:
                li.remove(str[i])
        if len(li)!=0:
            return str.index(li[0])
        else:
            return -1

发表于 2022-03-21 23:10:07 回复(0)

C++

许愿offer赶快来

位运算

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        long long sta = 0, flag = 0;
        for(auto &c : str) {
            int x = c - 'a';
            if(sta & (1 << x)) flag |= (1 << x);
            sta |= (1 << x);
        }
        for(int i = 0; i < str.size(); i++) {
            int x = str[i] - 'a';
            if((sta & (1 << x)) && !(flag & (1 << x))) return i;
        }
        return -1;
    }
};

发表于 2022-03-13 16:59:37 回复(0)