387. 字符串中的第一个唯一字符
2020-09-03 本文已影响0人
一角钱技术
387. 字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例：
s = "leetcode"
返回 0
s = "loveleetcode"
返回 2
提示：你可以假定该字符串只包含小写字母。
方法1：线性时间复杂度解法（Map）
算法思路：
- 遍历一遍字符串，然后把字符串中每个字符出现的次数保存在一个散列表中。这个过程的时间复杂度为 O(N)，其中 N 为字符串的长度。
- 接下来需要再遍历一遍字符串，利用散列表来检测遍历每个字符是不是唯一的，如果当前字符唯一，直接返回当前下标即可。第二次遍历的时间复杂度也是 O(N)。
参考代码1：
class Solution {
public int firstUniqChar(String s) {
if (s == null || s.length() == 0) {
return -1;
}
Map<Character, Integer> map = new HashMap<>();
for (char ch : s.toCharArray()) {
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < s.length(); i++) {
if (map.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}
复杂度分析：
- 时间复杂度：O(N) ，只遍历来两遍字符串，同时散列表中查找操作是常数时间复杂度的。
- 空间复杂度：O(N)，用到来散列表来存储每个字符串每个元素出现的次数。
方法2：ASCII码
算法思路：
利用单词的一个特性，字母最多为26个。声明一个长度为26的数组，利用 ASCII 码值计算每个元素的下标值，替换散列表记录每个元素出现的次数。
a-z：97-122
A-Z：65-90
0-9：48-57
参考代码2:
class Solution {
public int firstUniqChar(String s) {
if (s == null || s.length() == 0) {
return -1;
}
int[] freq = new int[26];
char[] chars = s.toCharArray();
for (char ch : chars) {
freq[ch - 'a']++;
}
for (int i = 0; i < chars.length; i++) {
if (freq[chars[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
}
复杂度分析：
- 时间复杂度：O(N)
- 空间复杂度：O(1)。
方法3：Java 本身的函数
参考代码3:
class Solution {
public int firstUniqChar(String s) {
if (s == null || s.length() == 0) {
return -1;
}
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
// 正向与反向的索引值相同，表示这个元素只出现过一次
if (s.indexOf(ch) == s.lastIndexOf(ch)) {
return i;
}
}
return -1;
}
}
参考代码4:
class Solution {
public int firstUniqChar(String s) {
if (s == null || s.length() == 0) {
return -1;
}
boolean[] notUniq = new boolean[26];
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!notUniq[ch - 'a']) {
if (s.indexOf(ch) == s.lastIndexOf(ch)) {
return i;
} else {
notUniq[ch - 'a'] = true;
}
}
}
return -1;
}
}
参考代码5:
class Solution {
public int firstUniqChar(String s) {
int res = -1;
for (char ch = 'a'; ch <= 'z'; ch++) {
// 获取当前字符的索引位置
int index = s.indexOf(ch);
// 比较当前字符正向与反向的索引值是否相同
if (index != -1 && index == s.lastIndexOf(ch)) {
res = (res == -1 || res > index) ? index: res;
}
}
return res;
}
}
以上谢谢大家，求赞求赞求赞！
