Необходимо найти сложность Big O для моего решения LeetCode problem.Какая большая сложность этого алгоритма
Я не могу оценить сложность из-за повторяющихся удалений из очереди при обнаружении повторяющегося символа, без которого он должен быть O (n) из-за одиночного цикла, проходящего через строку.
Проводка суть проблемы и мое решение для вашей справки:
Дана строка, найти длину самой длинной подстроки без повторяющихся символов.
Примеры:
Учитывая "abcabcbb", ответ "ABC", которой длина равна 3.
Учитывая "BBBBB", то ответ "б", с длиной 1.
Учитывая «pwwkew», ответ «WKE», с длиной 3. следует отметить, что ответ должен быть подстроку, «pwke» подпоследовательность и не подстроки.
Мое решение:
import java.util.Hashtable;
public class Solution {
public int lengthOfLongestSubstring(String s) {
Queue<Character> q = new LinkedList<Character>();
Hashtable<Character, Boolean> chars = new Hashtable<Character, Boolean>();
int maxLen = 0;
for (int i = 0; i < s.length(); i++)
{
char ch = s.charAt(i);
if (!chars.containsKey(ch))
{
q.add(ch);
chars.put(ch,true);
}
else
{
int len = q.size();
System.out.println(len);
while(q.peek()!=ch)
{
chars.remove(q.remove());
}
q.remove();
q.add(ch);
if (len > maxLen)
maxLen = len;
}
}
if (q.size() > maxLen)
return q.size();
return maxLen;
}
}
Но есть цикл while в цикле for, который можно было бы вызывать повторно. Разве это не изменит ситуацию? –
К сожалению, я смотрел решение веб-сайта, а не твое, я не видел этого цикла. В этом случае вы могли бы выяснить, что является наихудшим случаем для цикла while? Есть ли пример, в котором вы могли бы каждый if/else перейти к предложению else, а затем выполнить цикл while n раз? – Developer