蓝桥杯-每日刷题-025

稀疏数组

一、题目要求

• 题目描述
  稀疏数组就是数组中大部分内容都没有被使用（或都为0），在数组中仅有少部分空间使用，导致内存空间的浪费。
  为了节省空间，现在将下列稀疏数组进行压缩。
  数组为n行m列，存在一大部分是0表示该位置未被使用，非0则表示已经使用。
  将所有非0元素按照（行下标、列下标、元素值）存储下来，完成稀疏数组的压缩。
• 输入格式
  第一行为两个整数n,m(1<=n,m<=50)
  接下来n行，每行m个元素表示稀疏数组。
• 输出格式
  输出第一行先输出n,m,x。x表示非0元素数目 。接下来x行，每行输出行下标、列下标、元素值。
  按照行下标从小到大的顺序输出，如果同一行按照列下标从小到大的顺序输出。
• 输入样例
  10 10
  0 3 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  1 2 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 5 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 6 0 0
• 输出样例
  10 10 5
  0 1 3
  3 0 1
  3 1 2
  5 6 5
  9 7 6

二、完整代码

#include <iostream>
#include <vector>
#include <algorithm>

struct Element {
	int row;
	int col;
	int value;
};

bool compareElements(const Element& a, const Element& b) {
	if (a.row == b.row) {
		return a.col < b.col;
	}
	return a.row < b.row;
}

int main() {
	int n, m;
	std::cin >> n >> m;

	std::vector<std::vector<int>> sparseArray(n, std::vector<int>(m, 0));
	std::vector<Element> nonZeroElements;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			std::cin >> sparseArray[i][j];
			if (sparseArray[i][j] != 0) {
				Element element;
				element.row = i;
				element.col = j;
				element.value = sparseArray[i][j];
				nonZeroElements.push_back(element);
			}
		}
	}

	// 对非0元素按照行下标和列下标排序
	sort(nonZeroElements.begin(), nonZeroElements.end(), compareElements);

	// 输出结果
	std::cout << n << " " << m << " " << nonZeroElements.size() << std::endl;
	for (const Element& element : nonZeroElements) {
		std::cout << element.row << " " << element.col << " " << element.value << std::endl;
	}

	return 0;
}