Я написал код для двух подходов, чтобы найти первый уникальный символ в строке на LeetCode.
Постановка задачи: По заданной строке найдите в ней первый неповторяющийся символ и верните его индекс. Если он не существует, верните -1.
Примеры тестовых случаев:
s = "leetcode" вернуть 0.
s = "loveleetcode", возврат 2.
Подход 1 (O (n)) (поправьте меня, если я ошибаюсь):
class Solution {
public int firstUniqChar(String s) {
HashMap<Character,Integer> charHash = new HashMap<>();
int res = -1;
for (int i = 0; i < s.length(); i++) {
Integer count = charHash.get(s.charAt(i));
if (count == null){
charHash.put(s.charAt(i),1);
}
else {
charHash.put(s.charAt(i),count + 1);
}
}
for (int i = 0; i < s.length(); i++) {
if (charHash.get(s.charAt(i)) == 1) {
res = i;
break;
}
}
return res;
}
}
Подход 2 (O (n ^ 2)):
class Solution {
public int firstUniqChar(String s) {
char[] a = s.toCharArray();
int res = -1;
for(int i=0; i<a.length;i++){
if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {
res = i;
break;
}
}
return res;
}
}
В подходе 2, я думаю, сложность должна быть O (n ^ 2), так как indexOf здесь выполняется в O (n * 1).
Но когда я выполняю оба решения на LeetCode, я получаю время выполнения 19 мс для подхода 2 и 92 мс для подхода 1. Я запутался; почему это происходит?
Я предполагаю, что тесты LeetCode для малых и больших входных значений для лучших, худших и средних случаев.
Обновить:
Мне известно о том, что O (n ^ 2 алгоритмов) может работать лучше для определенных n <n1. В этом вопросе я хотел понять, почему это происходит в этом случае. т.е. какая часть подхода 1 делает его медленнее.
