Category Archives: php

php学习

面试题:一个字符串中找到第一个只出现一次的字符

今天逛水木，看到一道面试题，最简单的一个：“一个字符串中找到第一个只出现一次的字符”，大家争的没有一个结果，自己思考了一下，写了这么一个版本。主要考虑时间复杂度的降低，保证在o(n)内完成，组合利用hash表和queue两种数据结构完成。程序很简单，不解释

public static void main(String[] args){
char[] str = {‘a’,'b’,'c’,'b’,'d’,'d’,'a’,'f’,'a’,'g’};
HashMap hash = new HashMap();
Queue queue = new LinkedList();
for(int i=0;i hash.put(str[i], hash.get(str[i])!=null?hash.get(str[i])+1:1);
if(hash.get(str[i])==1){
queue.add(str[i]);
}
while(hash.get(queue.peek())>=2){
queue.poll();
}
}
System.out.println(queue.poll());
}