算法-如何查找第一个只出现一次的字符
2020-07-27 本文已影响0人
zzq_nene
方式一:
遍历每一个字符,然后取出遍历的当前字符与剩下的字符做比较,判断剩下的字符串中是否有当前遍历的这个字符,如果没有,则是在字符串中出现一次的,而第一个出现的,就是要查找的。
/**
* 使用便利的方式,时间复杂度是O(n^2)
* @param str
*/
private static void printFirstCharOnlyOnce(String str) {
for (int i = 0; i < str.length(); i++) {
// 截去第i个字符
String temp = str.substring(0, i) + str.substring(i + 1);
// 判断截去第i个字符后剩下的字符串中是否还有与第i个字符相同的字符
int index = temp.indexOf(str.charAt(i));
// 如果剩下的字符中没有与第i个字符相同的字符存在,则返回-1
// 第一次出现index=-1的时候,说明第i个字符就是第一个出现一次的字符
if (index == -1) {
String c = String.valueOf(str.charAt(i));
System.out.println(c);
break;
}
}
}
方式二:
直接使用hash表来查询,即使用HashMap来实现;首先遍历字符串的每一个字符,将字符作为HashMap的key,然后使用Integer作为HashMap的value,当key相同的时候,value就加1。遍历完之后,再对HashMap做遍历,找出key对应的value=1的key,第一个key就是查找第一个只出现一次的字符
/**
* 时间复杂度为O(n)
*/
private static void printFirstCharOnlyOnce(String str) {
HashMap<Character, Integer> hashMap = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
if (hashMap.containsKey(str.charAt(i))) {
int value = hashMap.get(str.charAt(i));
hashMap.put(str.charAt(i), value + 1);
} else {
hashMap.put(str.charAt(i), 1);
}
}
for (int i = 0; i < str.length(); i++) {
if (hashMap.get(str.charAt(i)) == 1) {
System.out.println(str.charAt(i));
break;
}
}
}
方式三:
借助ASCII码,将字符的ASCII码作为在int数组的索引位置,而该字符出现的次数就是对应的int数组的索引位置的值
private static void printFirstCharOnlyOnce(String str) {
int[] hash = new int[256];
for (int i = 0; i < str.length(); i++) {
int temp = str.charAt(i);
hash[temp]++;
}
for (int i=0;i<str.length();i++) {
int temp = str.charAt(i);
if (hash[temp] == 1) {
System.out.println(str.charAt(i));
break;
}
}
}