上三角矩阵压缩

矩阵压缩介绍

将三角矩阵压缩 到一维数组中去，相比原来节省了一般的空间。难点在如何将原理矩阵中的下标转换为一维数组中下标。其中主要使用的数学原理是等差数列求和公式。

等差数列求和公式：

$ S_n= a_1 n + \frac {n(n-1)d}{2} $

原理解析

上三角按行展开

注意：矩阵下标从0 开始，数组下标从0 开始

n*n 的矩阵,其中元素的矩阵下标（i，j），从矩阵下标转换为一维数组下标公式如下

$ index = i\times n-\frac{i\times(i-1)}{2} +(j-i) $

公式解释：

上三角矩阵的中某个元素前的所有元素的数目+元素所在行该元素前边的元素总数

∑r=0r=i−1(n−i)+∑c=ic=jc\sum_{r=0}^{r=i-1} (n-i) + \sum_{c=i}^{c=j} c

cpp 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// upperTriangular.cpp
#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> CreateUpperTriangular(int size,int startnum,int diagnoalValue,int emptyValue){
	vector<vector<int>> metrix = vector(size,vector(size,emptyValue));
	// 上三角矩阵的创建
	for(int i = 0;i<size;i++){
		for(int j = 0;j<size;j++){
			if (i==j) metrix[i][j] = diagnoalValue;
			else if(i<j){
				metrix[i][j] = startnum++;
			}else{
				continue;
			}
		}
	}
	
	
	return metrix;
}

void displayMetrix(vector<vector<int>>* metrix){
	for(auto it: *metrix){
		for(auto it2 : it ){
			cout<<it2<<" ";
		}
		cout<<endl;
	}
}

vector<int> compressUpperTriangular(vector<vector<int>>& metrix){
	int metrixCol = metrix.size();
	int arrsize = metrixCol*(metrixCol+1)/2; 
	vector<int> arr;
	arr.reserve(arrsize);  // 预分配空间提高效率
	for(int i = 0;i<metrixCol;i++){
		for(int j = 0;j<metrixCol;j++){
			if(i<=j){
				arr.emplace_back(metrix[i][j]);
			}
		}
	}
	return arr;
}

void displayArray(vector<int> *arr){
	for(auto it : *arr){
		cout<<it<<" ";
	}
	cout<<endl;
}

int findElementIndex(int num,vector<vector<int>> &metrix){
	//element i j
	int e_i = 0,e_j = 0;
	bool include = false;
	for(int i = 0;i<metrix.size();i++){
		for(int j=0;j<=metrix.size();j++){
			if(metrix[i][j] == num){
				include = true;
				cout<<"!!! find it position:";
				printf("(%d,%d)\n",i,j);
				e_i = i;
				e_j = j;
			}
		}
	}
	int index = -1;
	if (include){
		index = (e_i)*metrix.size()-(e_i)*(e_i-1)/2+(e_j-e_i);	
	}
	return index;
}

int main(){
	vector<vector<int>> metrix = CreateUpperTriangular(5,2,1,0);
	displayMetrix(&metrix);
	vector<int> arr = compressUpperTriangular(metrix);
	displayArray(&arr);
		
	// num=6
	int num = 6;
	int index= findElementIndex(num,metrix);
	if (index>=0){
		cout<<num<<" index: "<<index<<endl;
		cout<<arr[index]<<endl;
	}
}