Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.
Examples:
s = “l(fā)eetcode” return 0.
s = “l(fā)oveleetcode”, return 2. Note: You may assume the string contain only lowercase letters. 即找到字符串中第一個不重復(fù)的字母。
很自然的想到兩次遍歷來找到唯一的字符，同時利用字母只有26個的特點減少循環(huán)次數(shù)。
public int firstUniqChar(String s) { if (s.length() == 0) return -1; int[] test = new int[s.length()]; int count = 0; int result = -1; boolean found = true; for (int i = 0; i < s.length() && count < 27; i++) { if (test[i] == 1) continue; else count++; for (int j = i + 1; j < s.length(); j++) { if (test[j] == 1) continue; if (s.charAt(i) == s.charAt(j)) { found = false; test[i] = 1; test[j] = 1; } } if (found) { result = i; break; } found = true; } return result; }嵌套循環(huán)毫無疑問效率低下，這是想到使用鍵值對記錄每個字母的出現(xiàn)次數(shù)，同時利用hashmap去重的特性。
public int firstUniqChar1(String s) { if (s.length() == 0) return -1; int result = -1; Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (map.containsKey(c)) map.put(c, map.get(c) + 1); else map.put(c, 1); } for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (map.get(c) == 1) { result = i; break; } } return result; }雖然簡化了步驟，但是map的使用仍然需要較多的時間開銷。這是可以使用數(shù)組的1~26個位置代表a~z出現(xiàn)的次數(shù)。
public int firstUniqChar2(String s) { if (s.length() == 0) return -1; int result = -1; int[] record = new int[26]; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); int index = c - 'a'; record[index]++; } for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (record[s.charAt(i)-'a'] == 1) { result = i; break; } } return result; }新聞熱點
疑難解答
