【数据结构与算法】力扣刷题记之稀疏数组

深入理解稀疏数组

稀疏数组：概念与应用场景

第一节：稀疏数组的基础概念及应用场景

稀疏数组是一种特殊的数组数据结构，其特点是大部分元素为同一值或者为0。在实际应用中，稀疏数组常常被用来存储那些绝大多数元素为0的二维数据，如图像、矩阵等。一个典型的应用场景是图像处理中的位图压缩。

在不使用稀疏数组的情况下，如果直接用二维数组来表示稀疏性很高的数据结构，会导致大量的存储空间浪费和性能损耗。例如，对于一个大规模的稀疏矩阵，如果每个元素都占用存储空间，将会占用大量的存储空间。而且在处理这样的数据结构时，需要额外的时间复杂度来遍历和操作大量的0值元素。

引入稀疏数组可以有效解决上述问题。通过稀疏数组的存储方式，我们可以只存储非零元素及其位置信息，从而大大减少存储空间的占用。同时，在对稀疏数组进行操作时，可以极大地提高程序的运行效率。

第二节：实现稀疏数组的转换与应用

实现稀疏数组的转换

下面是一个简单的示例代码，用于将普通的二维数组转换为稀疏数组：

假设我们有一个普通的二维数组如下：

普通数组：

[[0, 0, 0, 0, 0], [0, 5, 0, 0, 0], [0, 0, 8, 0, 0], [0, 0, 0, 0, 0]]

我们希望将这个普通数组转换为稀疏数组。转换过程中，我们需要记录非零元素的位置和数值，并在稀疏数组的第一行记录原始数组的行数、列数和非零元素个数。具体转换过程如下：

遍历原始数组，记录非零元素及其位置：

非零元素 (1, 1) 值为 5 非零元素 (2, 2) 值为 8

将记录的非零元素及其位置转换为稀疏数组：

稀疏数组：

[[4, 5, 2], # 第一行记录原始数组的行数、列数和非零元素个数 [1, 1, 5], # 非零元素 (1, 1) 值为 5 [2, 2, 8]] # 非零元素 (2, 2) 值为 8

通过稀疏数组恢复出原始的普通数组。具体恢复过程如下：

根据稀疏数组的第一行信息创建一个全为0的普通数组。
遍历稀疏数组中的非零元素，根据其位置信息将对应的值填入新建的普通数组中。

代码语言：javascript复制

def convert_to_sparse_array(arr):
    sparse_arr = []
    rows, cols = len(arr), len(arr[0])
    count = 0

    # 遍历原始数组，记录非零元素及其位置
    for i in range(rows):
        for j in range(cols):
            if arr[i][j] != 0:
                sparse_arr.append([i, j, arr[i][j]])
                count  = 1

    # 在稀疏数组的第一行记录原始数组的行数、列数和非零元素个数
    sparse_arr.insert(0, [rows, cols, count])

    return sparse_arr

稀疏数组的恢复与应用

除了将普通数组转换为稀疏数组，我们还需要实现将稀疏数组恢复为普通数组的功能。下面是一个简单的示例代码：

代码语言：javascript复制

def restore_from_sparse_array(sparse_arr):
    rows, cols, count = sparse_arr[0]
    restored_arr = [[0 for _ in range(cols)] for _ in range(rows)]

    for i in range(1, count 1):
        row, col, val = sparse_arr[i]
        restored_arr[row][col] = val

    return restored_arr

探讨稀疏数组在题目以及实际开发中的应用场景

稀疏数组在实际项目中有许多应用场景，如图像处理、文本搜索、语音识别等。其中，最常见的应用场景是图像处理中的位图压缩。

在算法题领域中，稀疏数组也有广泛的应用。例如力扣（LeetCode）中的73题矩阵置零，就可以使用稀疏数组来进行优化，减少存储空间的占用。

力扣（LeetCode）73题矩阵置零的原题如下：

题目描述

给定一个m x n的矩阵，如果一个元素为0，则将其所在行和列的所有元素都设为0。请使用原地算法。

示例 1:

代码语言：javascript复制

输入:
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

代码语言：javascript复制

输入:
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出:
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

代码语言：javascript复制

// 稀疏数组压缩算法示例
void compress(int** ori_arr, int row, int col, int* arr_len, int*** com_arr) {
    int count = 0;
    for (int i = 0; i < row;   i) {
        for (int j = 0; j < col;   j) {
            if (ori_arr[i][j] != 0) {
                  count;
            }
        }
    }

    *com_arr = malloc((count   1) * sizeof(int*));
    (*com_arr)[0] = malloc(3 * sizeof(int));
    (*com_arr)[0][0] = row;
    (*com_arr)[0][1] = col;
    (*com_arr)[0][2] = count;

    int index = 1;
    for (int i = 0; i < row;   i) {
        for (int j = 0; j < col;   j) {
            if (ori_arr[i][j] != 0) {
                (*com_arr)[index] = malloc(3 * sizeof(int));
                (*com_arr)[index][0] = i;
                (*com_arr)[index][1] = j;
                (*com_arr)[index][2] = ori_arr[i][j];
                  index;
            }
        }
    }

    *arr_len = count   1;
}

// 稀疏数组恢复算法示例
void restore(int** ori_arr, int* arr_len, int*** com_arr) {
    int row = (*com_arr)[0][0];
    int col = (*com_arr)[0][1];

    for (int i = 0; i < row;   i) {
        for (int j = 0; j < col;   j) {
            ori_arr[i][j] = 0;
        }
    }

    for (int i = 1; i < *arr_len;   i) {
        int x = (*com_arr)[i][0];
        int y = (*com_arr)[i][1];
        int val = (*com_arr)[i][2];
        ori_arr[x][y] = val;
    }
}

稀疏数组压缩与恢复算法

思路分析

稀疏数组的压缩算法可以将数组进行压缩，从而减少存储空间的占用。具体来说，稀疏数组的压缩算法会按照一定的规则，将非零元素的值及其所在的位置信息记录下来，并将其存储为三元组的形式。

以下是稀疏数组的压缩算法思路：

遍历原始数组，统计非零元素的个数count。
创建一个新的二维数组com_arr，大小为(count 1) * 3，其中count 1表示非零元素的个数加上一行用于记录原始数组的行数、列数和非零元素的总个数。
将原始数组的行数、列数和非零元素的总个数分别存储在com_arr的第一行。
遍历原始数组，将非零元素的行、列和值存储在com_arr的后续行中。
返回压缩后的数组com_arr和非零元素的个数count 1。

稀疏数组的恢复算法则是根据压缩时的规则将压缩后的数据恢复为原始的数组数据。

以下是稀疏数组的恢复算法思路：