蓝桥杯-每日刷题-025

2023-12-21 11:31:59

稀疏数组

一、题目要求

  • 题目描述
    稀疏数组就是数组中大部分内容都没有被使用(或都为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;
}

文章来源:https://blog.csdn.net/m0_63642416/article/details/135125796
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。