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

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

深入理解稀疏数组


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


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


稀疏数组是一种特殊的数组数据结构,其特点是大部分元素为同一值或者为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


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


  1. 根据稀疏数组的第一行信息创建一个全为0的普通数组。
  2. 遍历稀疏数组中的非零元素,根据其位置信息将对应的值填入新建的普通数组中。
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


稀疏数组的恢复与应用


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

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:

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

示例 2:

输入:
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出:
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]
// 稀疏数组压缩算法示例
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;
    }
}


稀疏数组压缩与恢复算法


思路分析


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


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


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


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


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


  1. 根据压缩后的数组com_arr的第一行,获取原始数组的行数row、列数col。
  2. 创建一个新的二维数组ori_arr,大小为row * col,并将其所有元素初始化为0。
  3. 遍历com_arr的后续行,将非零元素的值和对应的位置信息恢复到ori_arr中。
  4. 返回恢复后的数组ori_arr。


相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
45 0
|
4月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
48 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
24 4
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
27 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
2月前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
24 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
96 0
|
2月前
力扣(LeetCode)数据结构练习题(2)
力扣(LeetCode)数据结构练习题(2)
32 0
|
2月前
|
存储
力扣(LeetCode)数据结构练习题
力扣(LeetCode)数据结构练习题
57 0