[抄题]:
给出一个字符串。找到字符串中第一个不重复的字符然后返回它的下标。如果不存在这样的字符,返回 -1
。
给出字符串 s = "lintcode"
,返回 0
。
给出字符串 s = "lovelintcode"
,返回 2
。
[暴力解法]:
时间分析:
空间分析:
[思维问题]:
[一句话思路]:
用cnt[256]数组存储即可
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
不用break,因为有一个值可行时,int函数就直接返回了
[二刷]:
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
[复杂度]:Time complexity: O(n) Space complexity: O(n)
[英文数据结构或算法,为什么不用别的数据结构或算法]:
用数组存储字母,所谓的hash
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
451. Sort Characters By Frequency 也是用256数组,再用heap排序
[代码风格] :
public class Solution {
/**
* @param s: a string
* @return: it's index
*/
public int firstUniqChar(String s) {
//corner case
if (s == null) {
return 0;
}
//put into cnt[]
char[] c = s.toCharArray();
int[] cnt = new int[256];
for (int i = 0; i < s.length(); i++) {
cnt[c[i]]++;
}
//return
for (int i = 0; i < s.length(); i++) {
if (cnt[c[i]] == 1) {
return i;
//break;
}
}
return -1;
}
}