Блог

У меня возникли проблемы с пониманием времени выполнения следующего решения для кода 1202.

 class Solution {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
    
    Map<Integer, List<Integer>> g = new HashMap<>();
    // O(V E)
    for(List<Integer> pair : pairs) {
        if(!g.containsKey(pair.get(0))) {
            g.put(pair.get(0), new ArrayList<>());
        }
        if(!g.containsKey(pair.get(1))) {
            g.put(pair.get(1), new ArrayList<>());
        }
        g.get(pair.get(0)).add(pair.get(1));
        g.get(pair.get(1)).add(pair.get(0));
    }
    
    char[] c = s.toCharArray();
    
    Set<Integer> seen = new HashSet<>();
    
    // O(V E * (VlogV))
    for(int i = 0; i < c.length; i  ) {
        if(seen.contains(i)) continue;
        List<Integer> index = new ArrayList<>();
        List<Character> temp = new ArrayList<>();
        dfs(i, g, seen, s, index, temp);
        Collections.sort(temp);
        Collections.sort(index);
        for(int j = 0; j < temp.size(); j  ) {
            c[index.get(j)] = temp.get(j);
        }
    }
    return new String(c);
    
}


private void dfs(int curr_node, Map<Integer, List<Integer>> g, Set<Integer> seen, 
                 String s, List<Integer> index, List<Character> temp) {
    
    if(seen.contains(curr_node)) return;
    index.add(curr_node);
    seen.add(curr_node);
    temp.add(s.charAt(curr_node));
    if(g.containsKey(curr_node)) {
        for (int i = 0; i < g.get(curr_node).size(); i  ) {
            dfs(g.get(curr_node).get(i), g, seen, s, index, temp);
        }   
    }
}
 

}

Пространство, которое я думаю, равно O(V E), где V-число отступов в строке, а E-число пар, когда мы строим наш график или dfs в каждом связном компоненте. Однако для среды выполнения я немного сбит с толку, поскольку построение графика в хэш-карте выполняется во время выполнения O(V E), им можно пренебречь из-за асимметричного поведения, поскольку оно меньше, чем время выполнения для приведенной ниже части кода для цикла. Я думаю, что время выполнения равно O(VlogV K * (V E)), где K-количество подключенных компонентов. VlogV-это время выполнения сортировки всех букв в строке, где V E-время выполнения DFS, так как мы выполняем DFS для всех подключенных компонентов, собираем индексы и символы и в конечном итоге сортируем все строки в подключенном компоненте и будем менять индексы строк ответов на основе нашего результата для каждого подключенного компонента. Что вы, ребята, думаете?