首页 > 试题广场 >

第一个只出现一次的字符

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

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

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

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

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

示例1

输入

"google"

输出

示例2

输入

"aa"

输出

-1

算法知识视频讲解

Java

鸭梨杉达

利用书中提到的，使用数组设计一个简易的哈希表解决此题

    public int FirstNotRepeatingChar (String str) {
        // write code here
        int [] newStr = new int[52]; // 创建一个数组，下标与字符一一对应
        Arrays.fill(newStr, 0);

        // 根据使用数组设计简易的哈希表（书中描述的方法）
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) <= 'Z') {
                int index = str.charAt(i) - 'A';  // 大写字母的对应的索引值
                newStr[index] += 1;  // 统计字符出现次数
            } else {
                int index = str.charAt(i) - 'a' + 26; // 小写字母对应的索引值
                newStr[index] += 1; // 统计字符出现次数
            }
        }
        for (int i = 0; i < str.length(); i++) {
            // 找到对应字符的索引，值是否为1
            if (str.charAt(i) <= 'Z' && newStr[str.charAt(i) - 'A'] == 1) {
                return i;
            } else  if(str.charAt(i) > 'Z' && newStr[str.charAt(i) - 'a' + 26] == 1){
                return i;
            }
        }
        return -1;
    }

发表于 2024-04-29 06:54:24 回复(0)

Java

牛客839384289号

public int FirstNotRepeatingChar (String str) {
    // write code here
    HashMap<Character ,Integer> map=new HashMap<>();
    for(int i=0;i<str.length();i++){
        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;
}

编辑于 2024-03-17 15:47:53 回复(0)

Java

加瓦加瓦_

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param str string字符串

* @return int整型

public int FirstNotRepeatingChar (String str) {

// write code here

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

if(str.indexOf(str.charAt(i))== str.lastIndexOf(str.charAt(i)))

return i;

}

return -1;

}

发表于 2023-11-07 10:12:53 回复(0)

Java

hi_wassuh

import java.util.*; 



public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    public int FirstNotRepeatingChar (String str) {
        int index=-1;
        if(str==null || str.length()<=0){
            return index;
        }else{
            char res = '\0';
            Map<Character, Integer> map = new LinkedHashMap<>();
            for(Character i:str.toCharArray()){
                map.put(i, map.getOrDefault(i,0)+1);
            }
            for(Map.Entry<Character, Integer> entry:map.entrySet()){
                if(entry.getValue()==1){
                    res=entry.getKey();
                    break;
                }
            }
            for(int i=0; i<str.length(); i++){
                if(res==str.charAt(i)){
                    index=i;
                }
            }
        }
        return index;
    }
}

发表于 2023-10-09 11:31:54 回复(0)

Java

怪我咯201905061626176

    public int FirstNotRepeatingChar (String str) {
        LinkedHashMap<Character, Integer> map = new LinkedHashMap<>(str.length());
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (map.containsKey(c)) {
                map.remove(c);
            } else {
                map.put(c, i);
            }
        }
        Optional<Map.Entry<Character, Integer>> first = map.entrySet().stream().findFirst();
        if (!first.isPresent()) {
            return -1;
        }
        return first.get().getValue();
    }

发表于 2023-09-06 15:37:07 回复(0)

Java

酷鹿路的跟屁虫

import java.util.*;

public class Solution {

public int FirstNotRepeatingChar(String str) {

HashMap<Character,Integer> map = new HashMap<>();

char[] s = str.toCharArray();

int n = s.length;

int ans = -1;

for(int i = 0; i < n; i++){

if(!map.containsKey(s[i])){

map.put(s[i],i);

}else{

map.remove(s[i]);

}

if(map.size() > 0) ans = Collections.min(map.values());

return ans;

}

发表于 2023-03-08 16:45:13 回复(0)

Java

我是一名可爱的程序员

Map<String, Integer> map = new LinkedHashMap();

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

String sData = String.valueOf(str.charAt(i));

if (map.containsKey(sData)) {

map.remove(sData);

} else {

map.put(sData, i);

}

if (map.size() == 0) {

return -1;

}

return map.entrySet().iterator().next().getValue();

发表于 2023-02-08 12:34:52 回复(1)

Java

喝杯白开水

public class Solution {

public static int FirstNotRepeatingChar(String str) {

int aa = str.length();

for (int i = 0; i < aa; i++) {

int j = 0;

while (j < aa){

if(i!=j && str.charAt(i) == str.charAt(j)){

break;

}

j++;

}

if(j == aa){

return i;

}

return -1;

}

发表于 2023-01-11 15:40:06 回复(0)

Java

BlueProtocol

import java.util.List;
import java.util.stream.Collectors;
import java.util.HashMap;

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        List<Character> collect = str.chars().mapToObj(c -> (char) c).collect(
                                      Collectors.toList());
        for (int i = 0; i < collect.size(); i++) {
            int indexOne = collect.indexOf(Character.valueOf(collect.get(i)));
            int lastIndexOf = collect.lastIndexOf(Character.valueOf(collect.get(i)));
            if (indexOne == lastIndexOf) {
                return indexOne;
            }
        }
        return -1;
    }
}

发表于 2022-10-08 16:08:05 回复(0)

Java

牛客733021646号

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        for(int i = 0; i < str.length(); i++){
            char x = str.charAt(i);
            String c = String.valueOf(x);
            
            String ss = str.substring(0,i) + str.substring(i+1);
            
            if(!ss.contains(c)){
                return i;
            }
        }
        return -1;
    }
}

发表于 2022-09-07 15:02:30 回复(0)

Java

牛客用户007

public class Solution {
    public int FirstNotRepeatingChar(String str) {

        for (int i = 0; i < str.length(); i ++) {
            int j = 0;
            for (; j < str.length(); j++) {
                if(i == j) continue;
                if (str.charAt(i) == str.charAt(j)) break;
            }
            if (j == str.length()) return i;
        }

        return -1;
    }
}

发表于 2022-09-03 13:23:49 回复(0)

Java

Healer777

    public int FirstNotRepeatingChar(String str) {
        if ( str.isEmpty() ) {
            return -1;
        }
        HashMap<Character, Integer> map = new HashMap<>();//用于保存每个字符已经对应的出现次数
        for (int i = 0 ; i < str.length() ; i++) {//统计各个字符出现的次数
            map.put(str.charAt(i),map.getOrDefault(str.charAt(i),0)+1);
        }
        for (int i = 0 ; i < str.length() ; i++) {//遍历map 找出第出现次数为1的字符
            if (map.get(str.charAt(i)) < 2) {
                return i;
            }
        }
        return -1;
    }

发表于 2022-08-26 02:41:55 回复(0)

Java

只会暴力做题

维护一个map存储每个字符出现的位置，如果字符重复出现就把位置置为-1，遍历map中的value取得除-1外的最小值

import java.util.*;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if (str == null || str.equals("")) {
            return -1;
        }
        Map<Character, Integer> map = new HashMap<>();
        int length = str.length();
        for (int i = 0; i < length; i++) {
            char c = str.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, -1);
            } else {
                map.put(c, i);
            }
        }
        int ans = Integer.MAX_VALUE;
        for (Integer value : map.values()) {
            if (value != -1) {
                ans = Math.min(ans, value);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

发表于 2022-05-23 14:02:25 回复(0)

Java

镜花水月_

import java.util.*;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        Map<Character,Integer> map = new LinkedHashMap<>();
        for(Character ch:str.toCharArray()){
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
        int num = -1;
        for(Character temp:map.keySet()){
            if(map.get(temp)==1){
                num = str.indexOf(temp);
                break;
            }
        }
        return num;
    }
}

发表于 2022-03-31 18:00:12 回复(0)

Java

牛客5287707号

public class Solution {
public int FirstNotRepeatingChar(String str) {

for (int i=0;i<str.length();i++){
String a = str.substring(i,i+1);
int ltmp = str.lastIndexOf(a);
int ftmp = str.indexOf(a);
if(ltmp == ftmp){
return i;
}
}
return -1;
}
}

发表于 2022-02-20 18:26:57 回复(0)

Java

浮鸟(BAT实习ing，目标外企~)

解法1：字符串index活用

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        for(int i=0;i<str.length();i++){
            char cur = str.charAt(i);
            // 前索引是否和后索引一致
            if(str.indexOf(cur)==str.lastIndexOf(cur))
                return str.indexOf(cur);
        }
        return -1;
    }
}

解法2：map

import java.util.*;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        // 解法2：map  key为字符，value为出现次数
        Map<Character, Integer> map = new HashMap<>();
        // 遍历str，构建map
        for(int i=0;i<str.length();i++){
            map.put(str.charAt(i),map.getOrDefault(str.charAt(i),0)+1);
        }
        // 二次遍历str，揪出首个value为1的key
        for(int i=0;i<str.length();i++){
            if(map.get(str.charAt(i))==1){
                return i;
            }
        }
        return -1;
    }
}

解法3：数组充当map

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        // 解法3： 数组充当map，由于char和int可以互相转，用char当索引
        
        // z的ascii码是大小写字母里最大的，注意需要+1才能遍历到再本身
        int array[] = new int['z'+1];
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            array[c] += 1;
        }
        // 二次遍历str，找出首个为1的
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if(array[c]==1){
                return i;
            }
        }
        return -1;
    }
}

发表于 2022-01-23 19:22:01 回复(0)

Java

bot4o7

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        boolean find = true;
        int i,j;
        for(i=0; i<str.length(); i++){
            for(j=0; j<str.length(); j++){
                if(str.charAt(j) == str.charAt(i)){
                    if( j != i){
                        find = false;
                        break;
                    }
                }
            }
            if(find){
                return i; 
            }
            find = true;
        }
        return -1;
    }
}

嵌套循环，但是这个时间复杂度可能高了吧。。。怎么降

发表于 2022-01-21 09:55:56 回复(0)

Java

^ǒ^月亮船^

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        
        int result = -1;
        
        if(str == null || "".equals(str)){
            return result;
        }
        
        //ASCII一共有128个
        int[] index = new int[128];
        
        char[] cs = str.toCharArray();
        
        //index记录每个字符的次数
        for(int i = 0 ; i < cs.length ; i++){
            index[cs[i]]++;
        }
        
        //搜索第一个只出现一次的字符
        for(int i = 0 ; i < cs.length ; i++){
            if(index[cs[i]] == 1){
                result = i;
                break;
            }
        }
        return result;
    }
}

发表于 2022-01-19 14:27:46 回复(0)