n*****a
发帖数: 55 | 1 面一个cloud start up， 问了find first non-duplicated char 的问题。 我先用
vector写了code, interviewer 又问如果不是ASCII , 是Unicode, 该怎么办？改用map
但是他说算法不是O(n). 还有什么别的方法吗？ | l*********8
发帖数: 4642 | 2 用unordered_map就是O(n)了吧？
map
【在 n*****a 的大作中提到】
: 面一个cloud start up， 问了find first non-duplicated char 的问题。 我先用
: vector写了code, interviewer 又问如果不是ASCII , 是Unicode, 该怎么办？改用map
: 但是他说算法不是O(n). 还有什么别的方法吗？
| n*****a
发帖数: 55 | 3 对的， 我当时没有想到unordered_map,看来要fail了。
【在 l*********8 的大作中提到】
: 用unordered_map就是O(n)了吧？
:
: map
| L*********r
发帖数: 9 | 4 For your reference.
public Character findFirstCharAppearingOnlyOnce(String s) {
Set dups = new HashSet();
Set uniques = new LinkedHashSet();
for ( Character c : s.toCharArray() ) {
if ( !dups.contains( c ) ) {
if ( uniques.contains( c ) ) {
uniques.remove( c );
dups.add( c );
} else
uniques.add( c );
}
}
if ( uniques.isEmpty() )
return null;
return uniques.iterator().next();
} |
|
