并查集(Union-Find) (图文详解)

article/2025/8/27 2:52:28

文章目录

  • 并查集基础知识
    • 定义
    • C++实现
    • 优化
  • 精选算法题(Java实现)
    • 实现并查集
    • 交换字符串中的元素
    • 最长连续序列 - 字节面试常考
    • 连通网络的操作次数
    • 最大岛屿数量 (三种解法)
    • 省份数量
    • 冗余连接
    • 冗余连接Ⅱ
    • 情侣牵手(困难)
    • 移除最多的同行或同列石头
    • 等式方程的可满足性
  • 结语

并查集基础知识

定义

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

主要构成：
并查集主要由一个整型数组pre[ ]和两个函数find( )、join( )构成。
数组 pre[ ] 记录了每个点的前驱节点是谁，函数 find(x) 用于查找指定节点 x 属于哪个集合，函数 join(x,y) 用于合并两个节点 x 和 y 。

作用：
并查集的主要作用是求连通分支数（如果一个图中所有点都存在可达关系（直接或间接相连），则此图的连通分支数为1；如果此图有两大子图各自全部可达，则此图的连通分支数为2……）

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

C++实现

class UnionFind{
public:UnionFind(int n){size = n;father = new int[n];for(int i = 0; i < n; i++){father[i] = i;}}//查看x的根节点 -> x所属集合int find(int x){int root = x;while(root != father[root]){root = father[root];}return root;}//将x和y染色为同一个颜色 -> 合并x和y的所属集合void merge(int x, int y){int rootX = find(x);int rootY = find(y);if(rootX == rootY) return;father[rootX] = rootY;//father[rooY] = rootX;}//路径压缩优化的查找int find(int x){int root = x;while(root != father[root]){root = father[root];}while(x != root){int fx = father[x];father[x] = root;x = fx;}return root;}//针对节点数量优化void merge(int x, int y){int rootX = find(x);int rootY = find(y);if(rootX == rootY) return;if(treeSize[rootX] < treeSize[rootY]){father[rootX] = rootY;treeSize[rootY] += treeSize[rootX];}else{father[rootY] = rootX;treeSize[rootX] += treeSize[rootY];}}
public:int *father, *treeSize, size;
};int P(UnionFind uf){for(int i = 0; i < uf.size; i++{cout << uf.color[i] << " ";} cout << endl;
}
int main(){int n = 10;UnionFind uf(n);uf.merge(0,1);P(uf);uf.merge(1,2);P(uf);uf.merge(5,9);P(uf);uf.merge(7,8);P(uf);uf.merge(8,6);P(uf);uf.merge(1,3);P(uf);uf.merge(6,1);P(uf);return 0;
}

问题思考：

  1. 极端情况下会退化成一条链
  2. 将结点数量多的接到结点少的树上，导致了退化
  3. 将较高的树接到较低的树上，导致了退化

面试一般要求优化到这一步
在这里插入图片描述LeetCode547 省份数量
在这里插入图片描述在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述

优化

在这里插入图片描述在这里插入图片描述在这里插入图片描述

精选算法题(Java实现)

实现并查集

/*** 实现并查集* @author: William* @time:2022-04-08*/
public class UnionFind {//记录每个节点的根节点int[] parent;//记录每个子集的节点数int[] rank;//记录并查集中的连通分量数量int count;public UnionFind1(int n) {count = n;parent = new int[n];for(int i = 0; i < n; i++) {parent[i] = i;}rank = new int[n];Arrays.fill(rank, 1);}public int find(int i) {if(parent[i] != i) parent[i] = find(parent[i]);return parent[i];}public void union(int x, int y) {int rootX = find(x), rootY = find(y);if(rootX != rootY) {if(rank[rootX] > rank[rootY]) {parent[rootY] = rootX;}else if(rank[rootX] < rank[rootY]) {parent[rootX] = rootY;}else {parent[rootY] = rootX;//相等的情况rank[rootX] += 1;}count--;//维护数量}}public int getCount() {return count;}public boolean connected(int x, int y) {return find(x) == find(y);}
}

交换字符串中的元素

/*** 交换字符串中的元素* @author: William* @time:2022-04-12*/
public class Num1202 {public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {if(pairs.size() == 0) {return s;}//1. 将任意交换的结点对输入并查集int n = s.length();UnionFind uf = new UnionFind(n);for(List<Integer> pair : pairs) {uf.union(pair.get(0), pair.get(1));}//2. 构建映射关系//char[] charArray = s.toCharArray();// key：连通分量的代表元，value：同一个连通分量的字符集合（保存在一个优先队列中）Map<Integer, PriorityQueue<Character>> map = new HashMap<>(n);for(int i = 0; i < n; i++) {int root = uf.find(i);
//			if (map.containsKey(root)) {
//              hashMap.get(root).offer(charArray[i]);
//          } else {
//              PriorityQueue<Character> minHeap = new PriorityQueue<>();
//              minHeap.offer(charArray[i]);
//              hashMap.put(root, minHeap);
//          }// 上面六行代码等价于下面一行代码，JDK 1.8 以及以后支持下面的写法map.computeIfAbsent(root,  key -> new PriorityQueue<>()).offer(s.charAt(i));}//3. 重组字符串StringBuilder sb  = new StringBuilder();for(int i = 0; i < n; i++) {int root = uf.find(i);sb.append(map.get(root).poll());}return sb.toString();}private class UnionFind {private int[] parent;private int[] rank;public UnionFind(int n) {this.parent = new int[n];this.rank = new int[n];for(int i = 0; i < n; i++) {this.parent[i] = i;this.rank[i] = 1;}}public void union(int x, int y) {int rootX = find(x), rootY = find(y);if(rootX != rootY) {if(rank[rootX] > rank[rootY]) {parent[rootY] = rootX;}else if(rank[rootX] < rank[rootY]) {// 此时以 rootY 为根结点的树的高度不变parent[rootX] = rootY;}else {parent[rootY] = rootX;// 此时以 rootX 为根结点的树的高度仅加了 1rank[rootX]++;}}}public int find(int x) {if(parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}}
}

最长连续序列 - 字节面试常考

/*** 最长连续序列 - 字节面试常考* @author: William* @time:2022-04-14*/
public class Num128 {public int longestConsecutive(int[] nums) {int ans = 0;//用来筛选某个数的左右连续数是否存在Map<Integer, Integer> map = new HashMap<>();//将连续的数字组成一个个集合UnionFind uf = new UnionFind(nums.length);for(int i = 0; i < nums.length; i++) {if(map.containsKey(nums[i])) continue;if(map.containsKey(nums[i] - 1)) {//往左判断uf.union(i, map.get(nums[i] - 1));}if(map.containsKey(nums[i] + 1)) {//往右判断uf.union(i, map.get(nums[i] + 1));}map.put(nums[i], i);//存储当前数}for(int i = 0; i < nums.length; i++) {//选出最长的数if(uf.find(i) != i) continue;//不是根节点ans = Math.max(ans, uf.rank[i]);}return ans;}class UnionFind{int[] parent;int[] rank;public UnionFind(int n) {this.parent = new int[n];this.rank = new int[n];for(int i = 0; i < n; i++) {this.parent[i] = i;this.rank[i] = 1;}}//这一步很关键 当时写的其他方法失败了public void union(int x, int y) {int rootX = find(x), rootY = find(y);if(rootX != rootY) {if(rank[rootX] < rank[rootY]) {int tmp = rootX;rootX = rootY;rootY = tmp;}parent[rootY] = rootX;rank[rootX] += rank[rootY];}}public int find(int x) {if(parent[x] != x){parent[x] = find(parent[x]);} return parent[x];}}
}

连通网络的操作次数

/*** 连通网络的操作次数* @author: William* @time:2022-04-14*/
public class Num1319 {public int makeConnected(int n, int[][] connections) {//网线数量太少的情况 n是电脑数if(connections.length < n - 1) return -1;UnionFind uf = new UnionFind(n);for(int[] connection : connections) {uf.union(connection[0], connection[1]);}//只需要操作连通数量-1次即可return uf.getCount() - 1;}class UnionFind{int count;int[] parent;int[] rank;public UnionFind(int n) {this.count = n;this.parent = new int[n];this.rank = new int[n];for(int i = 0; i < n; i++) {this.parent[i] = i;this.rank[i] = 1;}}public int getCount() {return count;}public void union(int x, int y) {int rootX = find(x), rootY = find(y);if(rootX != rootY) {if(rank[rootX] > rank[rootY]) {parent[rootY] = rootX;}else if(rank[rootX] < rank[rootY]) {parent[rootX] = rootY;}else {parent[rootY] = rootX;rank[rootX]++;}count--;}}public int find(int x) {return parent[x] == x ? x : find(parent[x]); }}
}

最大岛屿数量 (三种解法)

/*** 最大岛屿数量* @author: William* @time:2022-04-10*/
public class Num200 {class UnionFind{int count;int[] parent;int[] rank;public UnionFind(char[][] grid) {count = 0;int m = grid.length;//行数int n = grid[0].length;//列数parent = new int[m * n];rank = new int[m * n];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == '1') {parent[i * n + j] = i * n + j;//规律count++;}rank[i * n + j] = 0;}}}public int find(int i) {if(parent[i] != i) parent[i] = find(parent[i]);return parent[i];}public void union(int x, int y) {int rootX = find(x), rootY = find(y);if(rootX != rootY) {if(rank[rootX] > rank[rootY]) {parent[rootY] = rootX;}else if(rank[rootX] < rank[rootY]) {parent[rootX] = rootY;}else {parent[rootY] = rootX;//相等的情况rank[rootX] += 1;}count--;//维护数量}}public int getCount() {return count;}}public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int nr = grid.length;int nc = grid[0].length;int num_islands = 0;UnionFind uf = new UnionFind(grid);for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {grid[r][c] = '0';if (r - 1 >= 0 && grid[r-1][c] == '1') {uf.union(r * nc + c, (r-1) * nc + c);}if (r + 1 < nr && grid[r+1][c] == '1') {uf.union(r * nc + c, (r+1) * nc + c);}if (c - 1 >= 0 && grid[r][c-1] == '1') {uf.union(r * nc + c, r * nc + c - 1);}if (c + 1 < nc && grid[r][c+1] == '1') {uf.union(r * nc + c, r * nc + c + 1);}}}}return uf.getCount();}//dfs —— 重点掌握public int numIslands1(char[][] grid) {int count = 0;for(int i = 0; i < grid.length; i++) {//行数for(int j = 0; j < grid[0].length; j++) {//列数if(grid[i][j] == '1') {//满足条件就继续递归dfs(grid, i, j);count++;}}}return count;}private void dfs(char[][] grid, int i, int j) {//终止条件if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;grid[i][j] = '0';//分别向上下左右递归dfs(grid, i + 1, j);dfs(grid, i, j + 1);dfs(grid, i - 1, j);dfs(grid, i, j - 1);}//bfspublic int numIslands2(char[][] grid) {int count = 0;for(int i = 0; i < grid.length; i++) {for(int j =0; j < grid[0].length; j++) {if(grid[i][j] == '1') {bfs(grid, i, j);count++;}}}return count;}private void bfs(char[][] grid, int i, int j) {Queue<int[]> list = new LinkedList<>();list.add(new int[] {i, j});while(!list.isEmpty()) {int[] cur = list.remove();i = cur[0]; j = cur[1];if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {grid[i][j] = '0';list.add(new int[] {i + 1, j});list.add(new int[] {i - 1, j});list.add(new int[] {i, j + 1});list.add(new int[] {i, j - 1});}}}
}

省份数量

/*** 省份数量* @author: William* @time:2022-04-11*/
public class Num547 {public int findCircleNum(int[][] isConnected) {int provinces = isConnected.length;int[] parent = new int[provinces];//开辟一个parent数组 储存 某个节点的父节点for(int i =0; i < provinces;i++){parent[i] = i;}for(int i = 0; i < provinces; i++){for(int j = i + 1; j < provinces; j++){//两个节点只要是连通的就合并if(isConnected[i][j] == 1){union(parent, i, j);}}}int numProvinces = 0;//扫描parent数组 如果当前节点对应根节点 就是一个省份for(int i = 0; i < provinces; i++){if(parent[i] == i){numProvinces++;}}return numProvinces;}//支持路径压缩的查找函数public int find(int[] parent, int index){//父节点不是自己if(parent[index] != index){//递归调用查找函数 并把当前结果储存在当前节点父节点数组中parent[index] = find(parent, parent[index]);}//当父节点是本身时return parent[index];}//合并函数public void union(int[] parent, int index1, int index2){parent[find(parent , index1)] = find(parent, index2);}//dfspublic int findCircleNum1(int[][] isConnected) {int provinces = isConnected.length;boolean[] visited = new boolean[provinces];int numProvinces = 0;for(int i = 0; i < provinces; i++) {//如果该城市未被访问过，则从该城市开始深度优先搜索if(!visited[i]) {dfs(isConnected, visited, provinces, i);numProvinces++;}}return numProvinces;}private void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {for(int j = 0; j < provinces; j++) {//j时与i相连的邻居节点，相连且未被访问到if(isConnected[i][j] == 1 && !visited[j]) {visited[j] = true;//继续做深度优先搜索dfs(isConnected, visited, provinces, j);}}}
}

冗余连接

/*** 冗余连接* @author: William* @time:2022-04-11*/
public class Num684 {public int[] findRedundantConnection(int[][] edges) {int n = edges.length;int[] parent = new int[n + 1];for(int i = 1; i <= n; i++) {parent[i] = i;}for(int i = 0; i < n; i++) {int[] edge = edges[i];int node1 =edge[0], node2 = edge[1];//说明两个顶点不连通，当前边不会导致环出现if(find(parent, node1) != find(parent, node2)) {union(parent, node1, node2);}else {//已经连通成环 返回该边即可return edge;}}//这种情况表示没有return new int[0];}public void union(int[] parent, int x, int y) {parent[find(parent, x)] = find(parent, y);}public int find(int[] parent, int x) {if(parent[x] != x) {parent[x] = find(parent, parent[x]);}return parent[x];}
}

冗余连接Ⅱ

/*** 冗余连接Ⅱ  hard* @author: William* @time:2022-04-11*/
public class Num685 {public int[] findRedundantDirectedConnection(int[][] edges) {int n = edges.length;UnionFind uf = new UnionFind(n + 1);int[] parent = new int[n + 1];for (int i = 1; i <= n; ++i) {parent[i] = i;}int conflict = -1;int cycle = -1;for (int i = 0; i < n; ++i) {int[] edge = edges[i];int node1 = edge[0], node2 = edge[1];if (parent[node2] != node2) {conflict = i;} else {parent[node2] = node1;if (uf.find(node1) == uf.find(node2)) {cycle = i;} else {uf.union(node1, node2);}}}if (conflict < 0) {int[] redundant = {edges[cycle][0], edges[cycle][1]};return redundant;} else {int[] conflictEdge = edges[conflict];if (cycle >= 0) {int[] redundant = {parent[conflictEdge[1]], conflictEdge[1]};return redundant;} else {int[] redundant = {conflictEdge[0], conflictEdge[1]};return redundant;}}}
}class UnionFind{int[] parent;public UnionFind(int n) {parent = new int[n];for(int i = 0; i < n; i++) {parent[i] = i;}}public void union(int x, int y) {parent[find(x)] = find(y);}public int find(int x) {if(parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}
}

情侣牵手(困难)

/*** 情侣牵手 hard* @author: William* @time:2022-04-12*/
public class Num765 {//如果一对情侣恰好坐在了一起，并且坐在了成组的座位上，//其中一个下标一定是偶数，另一个一定是奇数，并且偶数的值 + 1 = 奇数的值。//例如编号数对 [2, 3]、[9, 8]，//这些数对的特点是除以 2（下取整）得到的数相等。public int minSwapsCouples(int[] row) {int len = row.length;int N = len >> 1;UnionFind uf = new UnionFind(N);for(int i = 0; i < len; i += 2) {uf.union(row[i] >> 1, row[i + 1] >> 1);}return N - uf.getCount();}private class UnionFind {private int[] parent;private int count;public int getCount() {return count;}public UnionFind(int n) {this.count = n;this.parent = new int[n];for(int i = 0; i < n; i++) {parent[i] = i;}}public int find(int x) {if(parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}public void union(int x, int y) {int rootX = find(x), rootY = find(y);if(rootX == rootY) return;parent[rootX] = rootY;count--;}}
}

移除最多的同行或同列石头

/*** 移除最多的同行或同列石头* @author: William* @time:2022-04-14*/
public class Num947 {public int removeStones(int[][] stones) {int sum = stones.length;UnionFind uf = new UnionFind(sum);for(int i = 0; i < sum; i++) {//j 是 i 下一个石头for(int j = i + 1; j < sum; j++) {int x1 = stones[i][0], y1 = stones[i][1];int x2 = stones[j][0], y2 = stones[j][1];if(x1 == x2 || y1 == y2) {//处于同行或同列uf.union(i, j);//粉碎石头}}}return sum - uf.getCount(); }class UnionFind{int count;int[] parent;int[] rank;public UnionFind(int n) {this.count = n;this.parent = new int[n];this.rank = new int[n];for(int i = 0; i < n; i++) {this.parent[i] = i;this.rank[i] = 1;}}public int getCount() {return count;}public void union(int x, int y) {int rootX = find(x), rootY = find(y);if(rootX != rootY) {if(rank[rootX] < rank[rootY]) {int tmp = rootX;rootX = rootY;rootY = tmp;}parent[rootY] = rootX;rank[rootX] += rank[rootY];count--;}}public int find(int x) {return parent[x] == x ? x : find(parent[x]); }}
}

等式方程的可满足性

/*** 等式方程的可满足性* @author: William* @time:2022-04-11*/
public class Num990 {public boolean equationsPossible(String[] equations) {int[] parent = new int[26];for(int i = 0; i < 26; i++) {parent[i] = i;}for(String str : equations) {if(str.charAt(1) == '=') {int x = str.charAt(0) - 'a';int y = str.charAt(3) - 'a';union(parent, x, y);}}for(String str : equations) {if(str.charAt(1) == '!') {int x = str.charAt(0) - 'a';int y = str.charAt(3) - 'a';//说明连过了if(find(parent, x) == find(parent, y)) {return false;}}}return true;}public void union(int[] parent, int x, int y) {parent[find(parent, x)] = find(parent, y); }public int find(int[] parent, int x) {while(parent[x] != x) {parent[x] = parent[parent[x]];x = parent[x];}return x;}
}

结语

并查集对我们来说是一个模板，无论理解还是不理解，都应该在笔试的时候可以快速写出来，很多时候看起来与连接有关的题，找到规律之后都能用并查集快速解出来


http://chatgpt.dhexx.cn/article/mGbjkJaA.shtml

相关文章

什么是 “并查集” ？

什么是 “并查集” ？

导语&#xff1a;并查集是一种精巧的算法&#xff0c;本身并不难理解&#xff0c;却很常用&#xff0c;在许多场景下都能找到并查集的身影。 本文作者封承成&#xff0c;年仅12岁&#xff0c;非常感谢他的投稿。 并查集是什么 并查集&#xff0c;是一种判断“远房亲戚”的算法。…
阅读更多...
并查集(Disjoint Set)

并查集(Disjoint Set)

目录 ❤️什么是并查集&#xff1f; &#x1f3b6;实现方法1 &#x1f414;实现方法2 &#x1f383;题目1 ❤️什么是并查集&#xff1f; 并查集是一种数据结构&#xff0c;用于处理一些不交集&#xff08;Disjoint sets&#xff0c;一系列没有重复元素的集合&#xff09;的…
阅读更多...
并查集

并查集

参考 https://www.cnblogs.com/asdfknjhu/p/12515480.html https://www.bilibili.com/video/BV13t411v7Fs?p3 https://leetcode-cn.com/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/ 一、基本概念 并查集是一种数据结构 并查集这…
阅读更多...
并查集（详细解释+完整C语言代码）

并查集（详细解释+完整C语言代码）

目录 1概论 2.树的表现形式 3.代码实现 3.1创立集合 3.2合并 3.3查询 3.4路径压缩 第一个方法&#xff1a;查找时优化 第二个方法&#xff1a;合并时优化&#xff08;加权标记法&#xff09; 4.完整代码 4.1优化前 4.2优化后 1概论 并查集是一种十分精巧且实用的树形…
阅读更多...
时间序列预测的一般步骤

时间序列预测的一般步骤

一、ARIMA模型概述 ​​ ARMA模型就是AR和MA的简单结合&#xff0c;同时包含了历史数值项和错误项。由于AR和MA模型都对时间序列有平稳性要求&#xff0c;ARMA模型也存在这个限制&#xff0c;因此我们将其拓展到ARIMA模型&#xff0c;其可以解决非平稳性问题。引入的差分概念是…
阅读更多...
时间序列预测算法总结

时间序列预测算法总结

时间序列算法 time series data mining 主要包括decompose&#xff08;分析数据的各个成分&#xff0c;例如趋势&#xff0c;周期性&#xff09;&#xff0c;prediction&#xff08;预测未来的值&#xff09;&#xff0c;classification&#xff08;对有序数据序列的feature提…
阅读更多...
基于深度学习的时间序列预测

基于深度学习的时间序列预测

# 技术黑板报 # 第十一期 推荐阅读时长&#xff1a;15min 前言 时间序列建模历来是学术和工业界的关键领域&#xff0c;比如用于气候建模、生物科学和医学等主题应用&#xff0c;零售业的商业决策和金融等。虽然传统的统计方法侧重于从领域专业知识层面提供参数模型&#xff0…
阅读更多...
预测类问题中的时间序列预测模型

预测类问题中的时间序列预测模型

前言&#xff1a;时间序列预测模型适用于含有时间变量的模型预测&#xff0c;对中短期的预测有着较好的结果&#xff0c;对长期预测不适用。本文重点介绍ARIMA模型的原理及代码实现。 其他模型总结&#xff1a;​【Python】Python中的经典时间序列预测模型总结_风度78的博客-C…
阅读更多...
Transformer 在时间序列预测中的应用

Transformer 在时间序列预测中的应用

2017年&#xff0c;Google的一篇 Attention Is All You Need 为我们带来了Transformer&#xff0c;其在NLP领域的重大成功展示了它对时序数据的强大建模能力&#xff0c;自然有人想要把Transformer应用到时序数据预测上。在Transformer的基础上构建时序预测能力可以突破以往的诸…
阅读更多...
【推荐收藏】11种比较常用的时间序列预测模型

【推荐收藏】11种比较常用的时间序列预测模型

时间序列及其预测是日常工作中建模&#xff0c;分析&#xff0c;预测的重要组成部分。 本文我们将从0开始介绍时间序列的含义&#xff0c;模型及其分析及其常用的预测模型。 文章目录 交流时间序列定义时间序列预测模型与方法原始数据朴素法简单平均法移动平均法指数平滑法一次…
阅读更多...
时间序列预测的20个基本概念总结

时间序列预测的20个基本概念总结

1、时间序列 时间序列是一组按时间顺序排列的数据点 比如&#xff1a; 每小时的气压每年的医院急诊按分钟计算的股票价格 2、时间序列的组成部分 时间序列数据有三个主要组成部分。 趋势季节性残差或白噪声 3、趋势 在时间序列中记录的长期缓慢变化/方向。 4、季节性 …
阅读更多...
时间序列-预测（Forcasting）:时间序列预测算法总结

时间序列-预测（Forcasting）:时间序列预测算法总结

一、背景介绍 绝大部分行业场景，尤其是互联网、量化行业，每天都会产生大量的数据。金融领域股票价格随时间的走势；电商行业每日的销售额；旅游行业随着节假日周期变化的机票酒店价格等； 我们称这种不同时间收到的，描述一个或多种特征随着时间发生变化的数据，为时间序列…
阅读更多...
时间序列预测 | ARMA应用指南

时间序列预测 | ARMA应用指南

ARMA可谓是时间序列最为经典常用的预测方法&#xff0c;广泛应有于涉及时间序列的各个领域。ARMA模型自出道以来&#xff0c;出场次数不可胜数。想必大家也都不陌生&#xff0c;常学常新&#xff0c;我们今天不妨再来回顾一遍&#xff5e;。 ARMA全称Autoregressive moving ave…
阅读更多...
时间序列预测的7种方法

时间序列预测的7种方法

import pandas as pd#取数 #dfpd.read_csv(jetrail.csv) #print(df.head()) ID Datetime Count 0 0 25-08-2012 00:00 8 1 1 25-08-2012 01:00 2 2 2 25-08-2012 02:00 6 3 3 25-08-2012 03:00 2 4 4 25-08-2012 04:00 2#pr…
阅读更多...
Transformer时间序列预测

Transformer时间序列预测

介绍&#xff1a; 提示&#xff1a;Transformer-decoder 总体介绍 本文将介绍一个 Transformer-decoder 架构&#xff0c;用于预测Woodsense提供的湿度时间序列数据集。该项目是先前项目的后续项目&#xff0c;该项目涉及在同一数据集上训练一个简单的 LSTM。人们认为 LSTM 在…
阅读更多...
时间序列预测的8种常用方法简介

时间序列预测的8种常用方法简介

时间序列预测的7种方法 1. 朴素预测法&#xff08;Naive Forecast) 如果数据集在一段时间内都很稳定&#xff0c;我们想预测第二天的价格&#xff0c;可以取前面一天的价格&#xff0c;预测第二天的值。这种假设第一个预测点和上一个观察点相等的预测方法就叫朴素法&#xff…
阅读更多...
常见的时间序列预测模型python实战汇总

常见的时间序列预测模型python实战汇总

最完整的时间序列分析和预测&#xff08;含实例及代码&#xff09;&#xff1a;https://mp.weixin.qq.com/s/D7v7tfSGnoAqJNvfqGpTQA 1 时间序列与时间序列分析 在生产和科学研究中&#xff0c;对某一个或者一组变量 x(t)x(t) ARIMA 模型对时间序列的要求是平稳型。因此&#…
阅读更多...
时间序列预测模型

时间序列预测模型

时间序列数据一般有以下几种特点&#xff1a;1.趋势(Trend) 2. 季节性(Seasonality)。 趋势描述的是时间序列的整体走势&#xff0c;比如总体上升或者总体下降。下图所示的时间序列是总体上升的&#xff1a; 季节性描述的是数据的周期性波动&#xff0c;比如以年或者周为周期&…
阅读更多...
【数据分析】基于时间序列的预测方法

【数据分析】基于时间序列的预测方法

时间序列预测 目录 时间序列预测1.时间序列介绍2.原始数据集3.导入数据4.检测时间序列的平稳性5.如何使时间序列平稳5.1 估计和消除趋势5.1.1 对数转换5.1.2 移动平均 5.2 消除趋势和季节性5.2.1 差异化5.2.2 分解 6.预测时间序列6.1 AR Model6.2 MA Model6.3 Combined Model6.…
阅读更多...
Matlab实现时间序列预测

Matlab实现时间序列预测

文章目录 一、数据准备二、时间序列预测分类1、输入为xt&#xff0c;输出是yt2、有x值&#xff0c;有y值&#xff1a;NARX(1)选择模型类型(2)选择输出&#xff0c;只有y_t(3)选择70%用来作为训练数据&#xff0c;15%用来作为验证使用&#xff0c;15%用来测试(4)选择delay(5)开始…
阅读更多...
推荐文章

Copyright @ 2022~2023