第一个出现两次的字母【LC2351】
Given a string s consisting of lowercase English letters, return the first letter to appear twice.
Note:
- A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b.
- s will contain at least one letter that appears twice.
新年快乐~
哈希表
- 思路：使用哈希表统计出现的字母及其次数，当某个字母出现次数为2时立即返回
- 实现
class Solution { public char repeatedCharacter(String s) { int[] charToCount = new int[26]; for (int i = 0; i < s.length(); i++){ charToCount[s.charAt(i) - 'a']++; if (charToCount[s.charAt(i) - 'a'] == 2){ return s.charAt(i); } } return 0; } }
。复杂度
- 时间复杂度：O ( n ) ，n为字符串长度
- 空间复杂度：O ( 1 )
位运算
- 思路：使用int类型变量代替哈希表，当一个已经出现过的字母再次出现时立即返回
- 实现
class Solution { public char repeatedCharacter(String s) { int state = 0; for (int i = 0; i < s.length(); i++){ int t = 1 << (s.charAt(i) - 'a'); if ((state & t ) != 0){ return s.charAt(i); } state |= t; } return 0; } }
。复杂度
- 时间复杂度：O ( n ) ，n为字符串长度
- 空间复杂度：O ( 1 )
