[Algorithm]First Non Repeating Character

一个很简单的方法就是扫两遍string，第一遍记录每一个字符的数量，更新map，第二次从左往右找到第一个出现次数是1的即可。但是当string很长的时候two-pass的方法效率不是很好，如果要求one-pass的话，我们第二遍扫map即可，因为当string很长是，相对于string，map的长度是很小的，所以我们在存map的时候，除了存count还需要把第一次出现的index也存下来，所以我们需要定义一个类，代码如下：

	public class FirstNonRepeatingCharacter {
	private class Counter {
	private int count;
	private int index;
	public Counter(int index) {
	count = 1;
	this.index = index;
	}
	}
	public char find(String s) {
	if (s == null)
	return ' ';
	int len = s.length();
	HashMap<Character, Counter> map = new HashMap<Character, Counter>();
	for (int i = 0; i < len; i++) {
	if (!map.containsKey(s.charAt(i)))
	map.put(s.charAt(i), new Counter(i));
	else
	map.get(s.charAt(i)).count++;
	}
	Iterator<Entry<Character, Counter>> iter = map.entrySet().iterator();
	int index = Integer.MAX_VALUE;
	char res = ' ';
	while (iter.hasNext()) {
	Entry<Character, Counter> entry = iter.next();
	if (entry.getValue().count == 1 && entry.getValue().index < index) {
	index = entry.getValue().index;
	res = entry.getKey();
	}
	}
	return res;
	}
	public static void main(String[] args) {
	test1();
	test2();
	test3();
	}
	//test cases
	private static void test1() {
	FirstNonRepeatingCharacter f = new FirstNonRepeatingCharacter();
	if (f.find("l") == 'l' &&f.find("aabbc") == 'c' && f.find("123456798") == '1')
	System.out.println("Test case 1 passed!");
	else
	System.out.println("Test case 1 failed");
	}
	private static void test2() {
	FirstNonRepeatingCharacter f = new FirstNonRepeatingCharacter();
	if (f.find("javavirtualmachine") == 'j' &&f.find("hahahahahahahab") == 'b')
	System.out.println("Test case 2 passed!");
	else
	System.out.println("Test case 2 failed");
	}
	private static void test3() {
	FirstNonRepeatingCharacter f = new FirstNonRepeatingCharacter();
	if (f.find("google") == 'l' && f.find("amazon") == 'm' && f.find("linkedin") == 'l')
	System.out.println("Test case 3 passed!");
	else
	System.out.println("Test case 3 failed");
	}
	}

view raw first non repeating character.java hosted with ❤ by GitHub