例如输入： jiaobuchongjdgfha
第一个出现一次的字符是 i 。
最容易想到的办法是写两个for循环遍历比较一下， 那这样的时间复杂度就是n^2。
那下面就来实现一个用空间换取时间的例子：
package com.jiaobuchong.demos;
/**
* Created by jiaobuchong on 16/6/10.
*/
public class FirstOnceChar {
public static void main(String[] args) {
char res = findFirstOnceChar("jiaobuchongjdgfha");
System.out.println(res);
}
private static char findFirstOnceChar(String charString) {
char[] chars = charString.toCharArray();
/**
* 对应ASCII码表的256个字符
* 数组的index就是字符, 值为字符出现的次数
*/
int[] arr = new int[256];
for (int i = 0; i < chars.length; i++) {
arr[chars[i]] += 1;
}
for (int i = 0; i < chars.length; i++) {
if (arr[chars[i]] == 1) {
return chars[i];
}
}
return ' ';
}
}
这种方式的时间复杂度最多也就2n, 相对还是要快点的。
