LeetCode387 First Unique Character in a String
LeetCode387 First Unique Character in a String
用户1665735
发布于 2019-02-19 14:30:01
发布于 2019-02-19 14:30:01
题目
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.
Examples:
s = “leetcode” return 0.
s = “loveleetcode”, return 2. Note: You may assume the string contain only lowercase letters. 即找到字符串中第一个不重复的字母。
方法一
很自然的想到两次遍历来找到唯一的字符，同时利用字母只有26个的特点减少循环次数。
public int firstUniqChar(String s) {
if (s.length() == 0) return -1;
int[] test = new int[s.length()];
int count = 0;
int result = -1;
boolean found = true;
for (int i = 0; i < s.length() && count < 27; i++) {
if (test[i] == 1) continue;
else count++;
for (int j = i + 1; j < s.length(); j++) {
if (test[j] == 1) continue;
if (s.charAt(i) == s.charAt(j)) {
found = false;
test[i] = 1;
test[j] = 1;
}
}
if (found) {
result = i;
break;
}
found = true;
}
return result;
}方法二
嵌套循环毫无疑问效率低下，这是想到使用键值对记录每个字母的出现次数，同时利用hashmap去重的特性。
public int firstUniqChar1(String s) {
if (s.length() == 0) return -1;
int result = -1;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c))
map.put(c, map.get(c) + 1);
else map.put(c, 1);
}
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.get(c) == 1) {
result = i;
break;
}
}
return result;
}虽然简化了步骤，但是map的使用仍然需要较多的时间开销。这是可以使用数组的1~26个位置代表a~z出现的次数。
public int firstUniqChar2(String s) {
if (s.length() == 0) return -1;
int result = -1;
int[] record = new int[26];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int index = c - 'a';
record[index]++;
}
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (record[s.charAt(i)-'a'] == 1) {
result = i;
break;
}
}
return result;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017年02月15日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录