Leetcode每日一题：电网维护解题思路与代码实现

Leetcode每日一题 —— 电网维护

题目链接：电网维护

思路
题看到一半第一反应，图+小顶堆/有序集合。但是看完题后，我想到的第一个思路居然是不考虑图，直接用多个链表/有序集合来维护电站状态，数组存放相同指针来确定一组电站。试一下卡卡。

代码

    public int processQueries(int c, int connections, int queries) {
        TreeSet<Integer> treeSets = new TreeSet[c + 1];
        for (int connection : connections) {
            int u = connection[0];
            int v = connection[1];
            if (treeSets[u] == null && treeSets[v] == null) {
                TreeSet<Integer> treeSet = new TreeSet<>();
                treeSet.add(u);
                treeSet.add(v);
                treeSets[u] = treeSet;
                treeSets[v] = treeSet;
            } else if (treeSets[u] == null) {
                TreeSet<Integer> treeSet = treeSets[v];
                treeSet.add(u);
                treeSets[u] = treeSet;
            } else if (treeSets[v] == null) {
                TreeSet<Integer> treeSet = treeSets[u];
                treeSet.add(v);
                treeSets[v] = treeSet;
            } else if (treeSets[u] != treeSets[v]) {
                TreeSet<Integer> big = treeSets[u].size() > treeSets[v].size() ? treeSets[u] : treeSets[v];
                TreeSet<Integer> small = treeSets[u].size() > treeSets[v].size() ? treeSets[v] : treeSets[u];
                while (!small.isEmpty()) {
                    int x = small.pollFirst();
                    treeSets[x] = big;
                    big.add(x);
                }
            }
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int query : queries) {
            int q = query[1];
            TreeSet<Integer> treeSet = treeSets[q];
            if (treeSet == null) {
                treeSet = new TreeSet<>();
                treeSet.add(q);
                treeSets[q] = treeSet;
            }
            if (query[0] == 2) {
                treeSet.remove(query[1]);
            } else {
                if (treeSet.contains(q)) {
                    list.add(q);
                } else if (treeSet.isEmpty()) {
                    list.add(-1);
                } else {
                    list.add(treeSet.first());
                }
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

时间复杂度：O(nlogc+qlogc)
空间复杂度：O(c)

优化思路
嗯。。。。。居然过了。。。。还以为会超时的。感觉如果前面初始化电站状态的时候如果改用图应该能有更好的效率，有空再试吧。

via - (author: 魔法师)