【一本通】行列转换问题

矩阵可以认为是N*M的二维数组。现在有一个巨大但稀疏的矩阵。
N，M范围是：1≤ N，M ≤100000，有K个位置有数据,K的范围是，1≤K100000。
矩阵输入的方式是从上到下(第1行到第N行)、从左到右(从第1列到第M列)扫描，记录有数据的坐标位置(x,y)和值(v)。这是按照行优先的方式保存数据的。现在要求按照列优先的方式输出数据,即从左到右、从上到下扫描,输出有数据的坐标和数值。

输入

第1行，3个整数N，M，K，其中1≤N，M，K ≤100000；下面有K行，每行3个整数：a，b，c，表示第a行第b列有数据c。数据在int范围内，保证是行优先的次序。

输出

1行，K个整数，是按照列优先次序输出的数。

样例输入

4 5 9
1 2 12
1 4 23
2 2 56
2 5 78
3 2 100
3 4 56
4 1 73
4 3 34
4 5 55

样例输出

73 12 56 100 34 23 56 78 55

提示
样例解释：

C语言实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100010  // 定义一个较大的常量，用于表示数组等的最大尺寸

int main() {
    int n, m, k;  // 分别表示矩阵的行数、列数、有数据的位置个数
    scanf(“%d %d %d”, &n, &m, &k);  // 输入矩阵的行数、列数、有数据的位置个数

    int x[MAX_SIZE];  // 存储有数据位置的行坐标
    int y[MAX_SIZE];  // 存储有数据位置的列坐标
    int d[MAX_SIZE];  // 存储对应位置的数据值
    int count[MAX_SIZE] = {0};  // 用于记录每列有数据的个数，初始化为0

    // 循环读取有数据的位置及对应的值，并统计每列有数据的个数
    for (int i = 0; i < k; i++) {
        scanf(“%d %d %d”, &x[i], &y[i], &d[i]);
        count[y[i]]++;  // 对应列的数据个数加1
    }

    int arr[MAX_SIZE];  // 定义指针数组，每个指针将指向对应列的数据存储数组
    // 为每列分配相应大小的内存空间，用于存储该列的数据
    for (int i = 1; i <= m; i++) {
        arr[i] = (int )malloc(count[i] * sizeof(int));
    }

    int index[MAX_SIZE] = {0};  // 用于记录每列当前存储数据的索引位置，初始化为0
    // 将读取的数据按照列优先顺序存储到对应的数组中
    for (int i = 0; i < k; i++) {
        arr[y[i]][index[y[i]]] = d[i];  // 将数据存入对应列的数组中
        index[y[i]]++;  // 对应列存储数据的索引位置加1
    }

    // 按照列优先顺序输出每列存储的数据
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < count[i]; j++) {
            printf("%d ", arr[i][j]);  // 输出当前列的每个数据
        }
    }

    // 释放之前为每列数据分配的内存空间
    for (int i = 1; i <= m; i++) {
        free(arr[i]);
    }

    return 0;
}

C++语言实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;  // 读取矩阵行数、列数、有数据的位置个数

    vector x(k);  // 存储有数据位置的行坐标
    vector y(k);  // 存储有数据位置的列坐标
    vector d(k);  // 存储对应位置的数据值
    vector count(m + 1, 0);  // 用于记录每列有数据的个数，初始化为0

    // 循环读取有数据的位置及对应的值，并统计每列有数据的个数
    for (int i = 0; i < k; ++i) {
        cin >> x[i] >> y[i] >> d[i];
        count[y[i]]++;  // 对应列的数据个数加1
    }

    vector<vector> arr(m + 1);  // 定义二维vector，外层对应列，内层存储每列的数据
    // 初始化二维vector，为每列创建对应的内层vector
    for (int i = 0; i <= m; ++i) {
        arr[i].resize(0);
    }

    // 将读取的数据按照列优先顺序存储到对应的二维vector中
    for (int i = 0; i < k; ++i) {
        arr[y[i]].push_back(d[i]);  // 将数据添加到对应列的内层vector中
    }

    // 按照列优先顺序输出每列存储的数据
    for (int i = 1; i <= m; ++i) {
        for (int num : arr[i]) {
            cout << num << " ";  // 输出当前列的每个数据
        }
    }
    return 0;
}

Java语言实现

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static final int MAX_SIZE = 100010;  // 定义一个较大的常量，用于表示相关集合等的最大容量

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取矩阵行数
        int m = scanner.nextInt();  // 读取矩阵列数
        int k = scanner.nextInt();  // 读取有数据的位置个数

        int[] x = new int[k];  // 存储有数据位置的行坐标
        int[] y = new int[k];  // 存储有数据位置的列坐标
        int[] d = new int[k];  // 存储对应位置的数据值

        int[] count = new int[m + 1];  // 用于记录每列有数据的个数，初始化为0

        // 循环读取有数据的位置及对应的值，并统计每列有数据的个数
        for (int i = 0; i < k; i++) {
            x[i] = scanner.nextInt();
            y[i] = scanner.nextInt();
            d[i] = scanner.nextInt();
            count[y[i]]++;  // 对应列的数据个数加1
        }

        ArrayList<ArrayList> arr = new ArrayList<>();  // 定义二维ArrayList，外层对应列，内层存储每列的数据
        for (int i = 0; i <= m; i++) {
            arr.add(new ArrayList<>());  // 初始化每列对应的内层ArrayList
        }

        // 将读取的数据按照列优先顺序存储到对应的二维ArrayList中
        for (int i = 0; i < k; i++) {
            arr.get(y[i]).add(d[i]);  // 将数据添加到对应列的ArrayList中
        }

        // 按照列优先顺序输出每列存储的数据
        for (int i = 1; i <= m; i++) {
            for (int num : arr.get(i)) {
                System.out.print(num + " ");  // 输出当前列的每个数据
            }
        }
    }
}