Bob
BAN USERpublic void FirstNonRepeatedCharacter(String s){
List<Character> candidates = new ArrayList<>();
HashSet<Character> alreadyExisted = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
if(!alreadyExisted.contains(s.charAt(i))){
if(candidates.contains(s.charAt(i))){
Character c = new Character(s.charAt(i));
candidates.remove(c);
alreadyExisted.add(c);
}
else
candidates.add(s.charAt(i));
}
}
System.out.println(candidates.get(0));
}
this code will have to traverse the String twice while I think that this code will be better:
public void FirstNonRepeatedCharacter(String s){
List<Character> candidates = new ArrayList<>();
HashSet<Character> alreadyExisted = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
if(!alreadyExisted.contains(s.charAt(i))){
if(candidates.contains(s.charAt(i))){
Character c = new Character(s.charAt(i));
candidates.remove(c);
alreadyExisted.add(c);
}
else
candidates.add(s.charAt(i));
}
}
System.out.println(candidates.get(0));
}
I think the radix sort is O (nlog(r)m) instead of O(n)
- Bob October 16, 2013