考研复习之数组稀疏矩阵合并区间算法(★)
2021/10/30 17:43:07
本文主要是介绍考研复习之数组稀疏矩阵合并区间算法(★),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数组的定义
数组:一旦被定义,它的维数和维界就不再该改变。
因此除了结构的初始化和销毁之外,数组只有存取元素和修改元素的操作。(★)
数组的存储
多维数组有两种映射方法:按行优先和按列优先
行优先:先储存行号较小的元素,行号相等先储存列号较小的元素。
列优先:反之
数组的压缩存储(了解)
压缩存储:多个值相同的元素只分配一个储存空间。对零元素不分配储存空间。 In order to save space.
特殊矩阵:具有许多相同元素或零元素,且有一定的分布规律性。如:对称矩阵,上下三角矩阵等。
特殊矩阵压缩方法:找出分布规律,把那些呈现规律性分布的、值相同的多个矩阵元素压缩到一个储存空间中。
稀疏矩阵(★)
矩阵元素远小于矩阵存储数量。
存储方法:将非零元素以及相应的行、列构成一个三元组。
稀疏矩阵的三元组既可以采用数组存储,也可以采用十字链表法存储。(★)
合并区间:
1.一个相同的结构体数组来存储最终结果,将所有区间左端点从小到大排序,以便于一次性从小到大合并区间。(注意快排的使用★)
2.从第一个区间开始判断,如果第二个区间的左端点小于第一个区间的右端点,那么两者重合可以合并。并且判断两个区间右端点的大小,取大值。
3.否则两者不重合重新定义区间左右端点、
#include <bits/stdc++.h> using namespace std; struct node{ int first; int last; }a[100]; struct node2{ int first; int last; }b[100]; bool rule(node a, node b) { if(a.first!=b.first) return a.first<b.first; else return a.last<b.last; } int main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>a[i].first>>a[i].last; } sort(a,a+n,rule); b[0].first=a[0].first; b[0].last=a[0].last; int count=0; for(int i=1;i<n;i++) { if(a[i].first<=b[count].last) { if(a[i].last>b[count].last) { b[count].last=a[i].last; } } else { count++; b[count].first=a[i].first; b[count].last=a[i].last; } } for(int i=0;i<=count;i++) { cout<<b[i].first<<" "<<b[i].last<<endl; } return 0; }
这篇关于考研复习之数组稀疏矩阵合并区间算法(★)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现