cpp 解法, 执行用时: 191 ms, 内存消耗: 108.9 MB, 提交时间: 2024-08-10 12:12:21

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<int> nxt(n - 1);
        iota(nxt.begin(), nxt.end(), 1);

        vector<int> ans(queries.size());
        int cnt = n - 1;
        for (int qi = 0; qi < queries.size(); qi++) {
            int i = queries[qi][0], r = queries[qi][1];
            while (nxt[i] < r) {
                cnt--;
                int tmp = nxt[i];
                nxt[i] = r;
                i = tmp;
            }
            ans[qi] = cnt;
        }
        return ans;
    }

    // 区间并查集
    vector<int> shortestDistanceAfterQueries2(int n, vector<vector<int>>& queries) {
        vector<int> fa(n - 1);
        iota(fa.begin(), fa.end(), 0);

        // 非递归并查集
        auto find = [&](int x) -> int {
            int rt = x;
            while (fa[rt] != rt) {
                rt = fa[rt];
            }
            while (fa[x] != rt) {
                int tmp = fa[x];
                fa[x] = rt;
                x = tmp;
            }
            return rt;
        };

        vector<int> ans(queries.size());
        int cnt = n - 1; // 并查集连通块个数
        for (int qi = 0; qi < queries.size(); qi++) {
            int l = queries[qi][0], r = queries[qi][1] - 1;
            int fr = find(r);
            for (int i = find(l); i < r; i = find(i + 1)) {
                fa[i] = fr;
                cnt--;
            }
            ans[qi] = cnt;
        }
        return ans;
    }
};

java 解法, 执行用时: 7 ms, 内存消耗: 76.6 MB, 提交时间: 2024-08-10 12:11:33

class UnionFind {
    public final int[] fa;

    public UnionFind(int size) {
        fa = new int[size];
        for (int i = 1; i < size; i++) {
            fa[i] = i;
        }
    }

    public int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }
}

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        UnionFind uf = new UnionFind(n - 1);
        int[] ans = new int[queries.length];
        int cnt = n - 1; // 并查集连通块个数
        for (int qi = 0; qi < queries.length; qi++) {
            int l = queries[qi][0];
            int r = queries[qi][1] - 1;
            int fr = uf.find(r);
            for (int i = uf.find(l); i < r; i = uf.find(i + 1)) {
                uf.fa[i] = fr;
                cnt--;
            }
            ans[qi] = cnt;
        }
        return ans;
    }
    
    // 记录跳转位置
    public int[] shortestDistanceAfterQueries2(int n, int[][] queries) {
        int[] nxt = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            nxt[i] = i + 1;
        }

        int[] ans = new int[queries.length];
        int cnt = n - 1;
        for (int qi = 0; qi < queries.length; qi++) {
            int i = queries[qi][0];
            int r = queries[qi][1];
            while (nxt[i] < r) {
                cnt--;
                int tmp = nxt[i];
                nxt[i] = r;
                i = tmp;
            }
            ans[qi] = cnt;
        }
        return ans;
    }
}

golang 解法, 执行用时: 131 ms, 内存消耗: 16.6 MB, 提交时间: 2024-08-10 12:10:34

func shortestDistanceAfterQueries(n int, queries [][]int) []int {
	nxt := make([]int, n-1)
	for i := range nxt {
		nxt[i] = i + 1
	}

	ans := make([]int, len(queries))
	cnt := n - 1
	for qi, q := range queries {
		for i, r := q[0], q[1]; nxt[i] < r; i, nxt[i] = nxt[i], r {
			cnt--
		}
		ans[qi] = cnt
	}
	return ans
}


// 区间并查集
func shortestDistanceAfterQueries2(n int, queries [][]int) []int {
	fa := make([]int, n-1)
	for i := range fa {
		fa[i] = i
	}
	// 非递归并查集
	find := func(x int) int {
		rt := x
		for fa[rt] != rt {
			rt = fa[rt]
		}
		for fa[x] != rt {
			fa[x], x = rt, fa[x]
		}
		return rt
	}

	ans := make([]int, len(queries))
	cnt := n - 1 // 并查集连通块个数
	for qi, q := range queries {
		l, r := q[0], q[1]-1
		fr := find(r)
		for i := find(l); i < r; i = find(i + 1) {
			fa[i] = fr
			cnt--
		}
		ans[qi] = cnt
	}
	return ans
}

python3 解法, 执行用时: 222 ms, 内存消耗: 44.8 MB, 提交时间: 2024-08-10 12:09:47

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        fa = list(range(n - 1))

        # 非递归并查集
        def find(x: int) -> int:
            rt = x
            while fa[rt] != rt:
                rt = fa[rt]
            while fa[x] != rt:
                fa[x], x = rt, fa[x]
            return rt

        ans = []
        cnt = n - 1  # 并查集连通块个数
        for l, r in queries:
            fr = find(r - 1)
            i = find(l)
            while i < r - 1:
                cnt -= 1
                fa[i] = fr
                i = find(i + 1)
            ans.append(cnt)
        return ans
        
    # 记录跳转位置
    def shortestDistanceAfterQueries2(self, n: int, queries: List[List[int]]) -> List[int]:
        ans = []
        nxt = list(range(1, n))
        cnt = n - 1
        for i, r in queries:
            while nxt[i] < r:
                cnt -= 1
                nxt[i], i = r, nxt[i]
            ans.append(cnt)
        return ans