剑指offer--第一个只出现一次的字符
今天刷题遇到这么个题目:
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）. 如 输入"google" ----> 输出 4
一开始只想到了HashMap,但考虑到HashMap是无序的,便又换个思路, 考虑到嵌套Map,
map(字符,map(索引,出现次数))
又想了下,其实这么实现显得麻烦了,理论上来说肯定不会这么麻烦...所以又换了条路,最后看到别人写到了LinkedHashMap就恍然大悟...然后想起来了 这个map是有序的.那么问题就简单了...代码如下
class Solution_32 {
public int FirstNotRepeatingChar(String str) {
Map<Character, Integer> map = new LinkedHashMap<>();
char s[] = str.toCharArray();
for (int i = 0; i < s.length; i++) {
if (!map.containsKey(s[i])) {
map.put(s[i], 1);
} else {
map.put(s[i], map.get(s[i]) + 1);
}
}
for (int i = 0; i < s.length; i++) {
if (map.containsKey(s[i]) && map.get(s[i]) == 1)
return i;
}
return -1;
}
}
输出结果:
image.png
但是反过来想,看到
for (int i = 0; i < s.length; i++) {
if (map.containsKey(s[i]) && map.get(s[i]) == 1)
return i;
}
又去重新遍历了一次str数组,那么这时候_已经和Map是否有序无关了,因为是按"google"去顺序匹配,而不是按照HashMap去顺序匹配的,在hashmap里通过散列的方式去查找,所以即便在hashmap里按照字母排序,e出现第一次在l出现第一次的前面,它还是会去匹配l的
所以即便把代码改成hashmap也是对的
class Solution_32 {
public int FirstNotRepeatingChar(String str) {
Map<Character, Integer> map = new HashMap<>();
char s[] = str.toCharArray();
for (int i = 0; i < s.length; i++) {
if (!map.containsKey(s[i])) {
map.put(s[i], 1);
} else {
map.put(s[i], map.get(s[i]) + 1);
}
}
for (int i = 0; i < s.length; i++) {
if (map.containsKey(s[i]) && map.get(s[i]) == 1)
return i;
}
return -1;
}
}
那么,LinkedHashMap在什么时候更适合呢?思考了下,如果题目改成这样:
- 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符, 如果没有则返回 -1（需要区分大小写）.
- google ---> l
这样就更适合LinkHashMap了
代码和结果如下:
class Solution32 {
public int FirstNotRepeatingChar(String str) {
//适合 找出第一个只出现一次的字符
Map<Character, Integer> map = new LinkedHashMap<>();
char s[] = str.toCharArray();
for (int i = 0; i < s.length; i++) {
if (!map.containsKey(s[i])) {
map.put(s[i], 1);
} else {
map.put(s[i], map.get(s[i]) + 1);
}
}
for (char k : map.keySet()) {
if (map.get(k) == 1) {
System.out.println(k + " : " + map.get(k));
break;
}
}
return -1;
}
}
image.png
总结:
LinkedHashMap是有序存取,其底层有一个双向循环链表来维护其存储顺序，遍历的时候是按照插入顺序来遍历的。HashMap是散列存储,由于最后都是按照str的顺序遍历的,所以用什么map都无所谓...以后多深入思考吧,别放弃太快~~ : )
