HashMap 空间换时间

发布： 分类： 评论： 阅读：

HashMap 的使用，很多时候都是为了空间换时间。

有时遇到字母或者字符时，还可以利用固定长度的数组代替 HashMap，比如字符为 Object[256] , 字母的话为 Object[26] 。

例题

leetcode 387. First Unique Character in a String

1
2
3
4
5
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.
  • 可以用hash表，统计每个字符出现的次数，然后再遍历一遍字符串，当当前元素出现的次数为1时，输出该字符的index。
  • 因为字符串中字符的种类最多256个，所以可以用数组模拟hash表。以字符的index作为key，出现次数作为value即可。
1
2
3
4
5
6
7
8
9
public int firstUniqChar(String s) {
    int[] count = new int[256];
    for(char ch:s.toCharArray())
        count[ch-'0'] += 1;
    for(int i=0;i<s.length();i++)
        if(count[s.charAt(i)-'0']==1)
            return i;
    return -1;
}