# 算法与数据结构面试题(21)-在一个字符串中找到第一个只出现一次的字符

qhshiniba 分享于 2014-12-30

# 题目

`在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。`

## 解题思路

```public class CharCount {

public void count(String str) {
if (str == null || str.length() == 0) {
return;
}
StringBuilder builder = new StringBuilder(str.length());
isContainsChar(str, str.length(), builder);
if (builder.length() == 0) {
System.out.println("无任何字符");
return;
}
// 有序hashmap来统计所有字符的个数,时间复杂度为O(n)
Map<Character, Integer> countMap = new LinkedHashMap<Character, Integer>();
for (int i = 0; i < builder.length(); i++) {
Character c = builder.charAt(i);
if (countMap.containsKey(c)) {
int num = countMap.get(c);
countMap.put(c, ++num);
} else {
countMap.put(c, 1);
}
}

System.out.println("含有字符: " + builder);
printCountInfo(countMap);
// 遍历map
if (!countMap.containsValue(1)) {
System.out.println("该字符串中不含有只出现一次的字符");
return;
}
Set<Map.Entry<Character, Integer>> set = countMap.entrySet();
Iterator<Entry<Character, Integer>> iterator = set.iterator();
while (iterator.hasNext()) {
Entry<Character, Integer> entry = iterator.next();
if (entry.getValue() == 1) {
System.out.println("第一个只出现一次的字符为  : "
+ entry.getKey());
return;
}
}

}

private void isContainsChar(String str, int length, StringBuilder builder) {
str = str.toLowerCase();
Pattern pattern = Pattern.compile("[a-z]+");
Matcher matcher = pattern.matcher(str);
int k = 0;
while (k < length) {
if (matcher.find()) {
builder.append(matcher.group());
if (matcher.end() == length) {
// System.out.println("over");
break;
}
}
k++;
}
}

private void printCountInfo(Map<Character, Integer> map) {
if (!map.isEmpty()) {
Set<Entry<Character, Integer>> set = map.entrySet();
Iterator<Entry<Character, Integer>> iter = set.iterator();
while (iter.hasNext()) {
Entry<Character, Integer> entry = iter.next();
System.out.println(String.format("%c : %d", entry.getKey(),
entry.getValue()));
}
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
String[] strArray = { "123456",// 测试无字符的情况,能否区分数字
"“   \$@!-=)(&^%#@!",// 测试无字符的情况,能否区分特殊符号
"asdfsewrewe",// 测试小写字符的统计
"ASDFDSFWEGSDFSD",// 测试大写字符的统计
"12324aasdfds",// 测试小写字符和非字符组合的情况
"12324ASDFDSFWEGSDFSD",// 测试大写字符和非字符组合的情况
"aasdfdsASDFDSFWEGSDFSD",// 测试小写和大写组合的情况
"aasdfdsASDFDSFWEGSDFSD“   \$@!-=)(&^%#@!",// 测试小写、大写和非字符组合的情况
null,// 测试空字符串的情况
""// 测试字符串大小为0的情况
};
CharCount charCount = new CharCount();
for (String str : strArray) {
System.out.println(String.format("字符串 %s中字符分配情况：", str));
charCount.count(str);
System.out.println("=================================");
}

}
}```

```字符串 123456中字符分配情况：

=================================

=================================

a : 1
s : 2
d : 1
f : 1
e : 3
w : 2
r : 1

=================================

a : 1
s : 4
d : 4
f : 3
w : 1
e : 1
g : 1

=================================

a : 2
s : 2
d : 2
f : 1

=================================

a : 1
s : 4
d : 4
f : 3
w : 1
e : 1
g : 1

=================================

a : 3
s : 6
d : 6
f : 4
w : 1
e : 1
g : 1

=================================

a : 3
s : 6
d : 6
f : 4
w : 1
e : 1
g : 1

=================================

=================================

=================================
```

×
• 登录
• 注册

×