华为机试牛客刷题之HJ59 找出字符串中第一个只出现一次的字符

HJ59 找出字符串中第一个只出现一次的字符

描述
对于给定的字符串，找出第一个只出现一次的字符。如果不存在，则输出 −1。

输入描述：
在一行上输入一个长度为 1≦len(s)≦10^3 、仅由小写字母构成的字符串 s。

输出描述：
如果存在只出现一次的字符，输出第一个满足条件的字符；否则，直接输出 −1。

示例1

输入: asdfasdfo
输出: o

示例2

输入: aabbcc
输出: -1

思路是用一个LinkedHashMap来保存字符和对应的出现次数。然后循环遍历字符串的每个字符，统计每个字符出现的次数。最后遍历这个LinkedHashMap的entrySet，寻找第一个value等于1的entry。一旦找到，就输出该字符，并标记found为true，然后break跳出循环。如果遍历完了都没找到，就输出-1。

import java.util.Scanner;
import java.util.LinkedHashMap;
import java.util.Map;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();Map<Character,Integer> map = new LinkedHashMap();for(int i=0;i < str.length();i++){char temp = str.charAt(i);if(map.containsKey(temp)){int count = map.get(temp)+1;map.put(temp,count);}else{map.put(temp,1);}}boolean found = false;for(Map.Entry<Character,Integer> entry : map.entrySet()){if(entry.getValue() == 1){System.out.println(entry.getKey());found = true;break;}}if (!found) {System.out.println(-1);}}}
}

改进点：

使用数组替代LinkedHashMap可优化空间复杂度为O(1)（假设ASCII字符集）。
第二次遍历直接遍历原字符串而非LinkedHashMap，可提前终止。

优化代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextLine()) {String str = in.nextLine();int[] count = new int[256]; // ASCII字符集for (int i = 0; i < str.length(); i++) {count[str.charAt(i)]++;}boolean found = false;for (int i = 0; i < str.length(); i++) {if (count[str.charAt(i)] == 1) {System.out.println(str.charAt(i));found = true;break;}}if (!found) {System.out.println(-1);}}}
}

优化说明

效率提升：
- 空间优化：数组代替LinkedHashMap，空间复杂度降至O(1)。
- 提前终止：第二次遍历字符串时，找到第一个计数为1的字符即可返回，无需遍历整个Map。
适用性：
- 假设字符范围为ASCII（0-255），若需支持Unicode，可调整数组大小或改用HashMap。